Hi. I am trying to learn how to traverse a graph so that I can make my bots traverse a terrain. I am currently reading the book "Programming Game AI by Example" by Mat Buckland. This book is very informative and I put together the following demo in a few hours. http://www.brandonfogerty.com/flash_stuff/show_movie.php?movie=AI&src=1&width=550&height=400 However I have a question about how to find the closest node. For example, imagine a bot sees the player and decides to chase him. The player ends up being to fast for the bot and finds a good hiding place so the bot decides to go back on his normal node traversal routine. The problem is, given the bots new location, this location is not on a node but at an arbitrary location, how could the bot efficiently traverse the graph tree to find the closest node. A brute force method would say, loop through all the nodes and find the smallest distance from the bot to the node. Once the closest node has been found, then go to that node however if you have 1 million nodes, that would be pretty inefficient. What is a common game way to tackle this problem? Thanks in advance!

Quote: The problem is, given the bots new location, this location is not on a node but at an arbitrary location

How is this possible? I don't know much about AI programming, but if you leave your graph then how are you making use out of it?

Well, I don't know if it's what you're looking for, but if you can manage to always be in a node from the graph, then finding the closest neigbouring node can be done using several algorithms. You could look into the following if you aren't already familiar with them: Dijkstra, Floyd, Warshall,...

Jeroen

A popular strategy is to use what's called a "navmesh". You basically cover the floor with convex polygons or triangles or squares or whatever, and each shape is a node in the graph. You keep track of which node the entity is on as it moves around, where each node is now a geometric region (instead of a single point).

Quote: Original post by akaitora
The problem is, given the bots new location, this location is not on a node but at an arbitrary location, how could the bot efficiently traverse the graph tree to find the closest node. A brute force method would say, loop through all the nodes and find the smallest distance from the bot to the node. Once the closest node has been found, then go to that node however if you have 1 million nodes, that would be pretty inefficient.

In practical terms it is unlikely that a particular bot is associated with path graph comprised of one million nodes, the cost of brute forcing distance checks on, say, a realistic 50 nodes maximum wouldn't be much at all. From a theoretical point of view, if there were a million nodes then some kind of spatial partitioning or hashing scheme would help to reduce the number of nodes to check.

dmatter, I am currently using a brute force method. So you wouldn't think that is ai blasphemy would you? =)

Not at all, the fact is you have N possible nodes and at least one of those is the nearest, you have to check them all to know which it is going to be. If there were a large number of nodes in total then there are tricks (see my last post) to reduce the number of potentials but you'd still have to brute force through those potentials.

If you wanted you could introduce heuristics, for example if the bot knows it hadn't travelled very far before the player got away then rather than find the nearest node it could just travel back to its last visited node; this isn't guaranteed to be the nearest node but it is going to be nearby.

Quote: Original post by dmatter
Not at all, the fact is you have N possible nodes and at least one of those is the nearest, you have to check them all to know which it is going to be. If there were a large number of nodes in total then there are tricks (see my last post) to reduce the number of potentials but you'd still have to brute force through those potentials.

If you wanted you could introduce heuristics, for example if the bot knows it hadn't travelled very far before the player got away then rather than find the nearest node it could just travel back to its last visited node; this isn't guaranteed to be the nearest node but it is going to be nearby.

Reread Vorpy's short reply. If you use a navmesh, then you are ALWAYS in a node, and your problem simply never arises.

Yay for navmeshes.

But if you dont want to use navmesh and want to be creative, you could pre-calculate a voronoi diagram of your nav graph and use it to get the closest node. Of course, getting the closest node is flawed itself, because the closest node might very well be on the other side of a wall.

Another (better, simpler) way is to run the pathfinding system even when you dont need it, to always keep track of your current node.

Quote: Original post by Steadtler
But if you dont want to use navmesh and want to be creative, you could pre-calculate a voronoi diagram of your nav graph and use it to get the closest node.

Even cooler: Create a Voronoi partition of your world based not on predefined nodes, but on the obstacles. Then use the nodes of this graph as your pathfinding nodes. Edges in the Voronoi diagram become "highways" in your world. All-in-all it's pretty cool because it produces relatively low-complexity graphs (lower complexity than, say, visibility graphs).