How should I provide a navigation system for a world with infinite space?

Question

The world is generated by perlin noise chunks and will only be saved once that chunk has been generated. It will also not necessarily have one obvious (to the user) central point anywhere in the world, but the chunks start at 0,0 and go in all directions.

What would work to help people find their relative position to another user or buildings?

A few ideas that have crossed my mind:

• Area names - creating the names procedurally might be an issue though (?) and doesn't entirely solve the issue (until you're used to the names, they will mean nothing to you)
• A grid system, then there is something to be relative to - from a user's point of view, this is pretty tedious and I can't imagine it is really a good solution (UI-wise)
• A compass that shows the direction to chunk 0,0 and the distance from it, this is the closest solution for me so far
• A mini map of the environment would work, but only for local areas otherwise the minimap would end up taking up the entire screen or having to scroll for ages to reach other areas

Or some combination of the above.

Any thoughts on the above or other suggestions would be greatly appreciated.

Answer 1

What about a grid system centered on the player? That is, just indicate locations as, say, "13 foos south and 6 west of you." That way, you don't need to designate any specific location as the origin.

Arrows pointing to nearby interesting things (and more distant bigger things) and giving the distance to them could also help with local navigation, and could complement the grid system nicely. Letting the player designate and/or name locations could also work.

For mini-maps, Philipp's suggestion of allowing zooming seems good.

Answer 2

It isn't really possible to have an 'infinite' space. You need some way to index the positions, so if you used an int then the maximum size would be MAX_INT.

You can use bigger index data types. Maybe a long or even something more esoteric like a long long long long. There are some ways to have numbers that can grow arbitrarily but they will add performance/memory overhead.

At the end of the day you will still be bound by the memory of the system.

Do avoid floats/doubles at they loose precision the further away from 0.0 you go. Look at the Minecraft end of the world videos.

So it's probablly better to use a 'fixed' sized world and just make it very very very big. With a fixed sized world you could use a GPS system. You can also make the world 'wrap' around so it's like a sphere.

Having said that I wouldn't give the player raw coordinates to have to deal with. You are just making them remember stuff and giving them extra work. Place names seem hard to implement in a procedural system. Seems like they would come out too uniform (ie you would be naming square regions rather then points of interest).

It seems like having a 'waypoint' would be the way to go. Combine A map, compass markers, plus a list of waypoints that the player can turn on/off and possibly a 'pillar of light' at the position' so it can be seen on the horizon (that only makes sense for 3D games) and a fined grained marker at the point on the ground. Also let them set their own waypoint.

As a simple version would just have a direction (an angle, or arrow that points there) and distance to target. The problem with that is the player sometimes has to go around the long way to avoid obstacles rather than straight in the direction.

You can also use the waypoint system for 'points of interest' within a range like Skyrim does for dungeons.