Sign in to follow this  
Max Power

pathfinding on a 2d map

Recommended Posts

I am working on a 3d game on a terrain made of a regular grid of vertices and faces. Some faces should not be walkable because too steep, difficult terrain, underwater etc.

 

My only experience with pathfinding ai so far is within a voxel world where I used a kind of floodfill(??) approach: try every possible way until finding the destination by chance and remember how to get there as fast as possible. But my map now is pretty large and destinations may be very far, so I guess this would be too slow for a large number of AIs.

 

Any suggestions?

Share this post


Link to post
Share on other sites

To add to what everyone has said so far, start with A*. There's essentially no difference in the pathfinding between a 2d and a 3d map, they both break down into graphs of nodes (places in the world) and edges (the connection between places). A grid map with holes in it is just missing some edges.

Share this post


Link to post
Share on other sites

Thanks for replies. I will look into this A*. Maybe it's not so different from what I already did in my other game. It will probably just come down to finding the right resolution of waypoints to get decent performance, so I might have to skip some terrain nodes between waypoints.

Share this post


Link to post
Share on other sites

The "flood fill" algorithm is essentially Dijkstra's. A* is an optimisation of it.

 

You can use these even if you don't have a regular grid on your ground, just *pretend* that you do have such a regular grid, and run the algorithm anyway. You only need to write a function "can I pass this point", which needs to be conservative enough that your moving units can actually pass that point to its adjacent points without encountering any new obstacles - so the "can I pass this point" function might need to take into account the distance of nearby objects, and return false even if the point itself appears passable.

 

Anyway, give it a go, and you'll easily get something that works.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this