GPS system pathfinding

I’m making an open-world game and I need to work out a way to find a gps route between locations. I’ve established that I’ll need to determine the closest road object to each location and then find a route between them. Right now, I’m using an mp_grid system with squares the size of the road objects. However, there are several problems with this.

Not every road object is active at once. The way the open world system works is that it connects several rooms and loads their objects into one room that is played in, shifting, deactivating and destroying objects as necessary. Obviously, that means that only nearby roads will actually exist in the room.

Some of the roads are diagonal, so it becomes a bit weird when working with a straight grid.

Once the world is of large enough size, it will be very impractical to have an entire open world in 256x256 chunks.

I’m thinking that, once I have a functioning map screen, this will become easier as the world and it’s roads are summarised into a to-scale image. In that case, how would I find a route from one point to another on this map? (It will be a single sprite, unless there is an advantage to using two sprites, one for the land and one for the roads.)

Or is there a better alternative?

An example of a road map like the one I want, from GTA IV.
 

Attachments

Rob

Member
If you could save the locations of all roads to one grid when the game starts, you could just use that grid to path find, and then load the necessary chunks as the player gets to them.

I guess you could load each chunk in order starting from top left and set each cell to 0 or 1 and hide all of this behind a loading screen. You could even just save this grid to a file that you create when you're done messing with the map so that it doesn't need to be re-created every time the game launches.
 
Thanks. I think I’ve solved the problem, I’ll do this but on the final world map rather than in the world, as it will make for a more efficient grid. Thanks for the help.
 
Top