Leges Motus Progress: Pathfinding with Ray Casting and A*


Since our last update, the Leges Motus team has been working hard on a new portion of the AI: pathfinding. Having an AI that jumps around randomly, trying to slowly get towards the goal, won’t get you very far in terms of realistic simulation or believable gameplay. We decided to make a pathfinding system that would allow our AIs to find paths to any point on the map.

Here is a screenshot of our pathfinding system in progress – you can see the line showing the calculated path to the goal:

Testing the Leges Motus pathfinding system

A test version of the Leges Motus pathfinding system.

We could not simply use a standard A* algorithm based on a grid of connected space, because it would assume the ability to turn in mid-air, which is not possible in zero-gravity. We decided, however, that we still wanted to try to use A* as the final pathfinding algorithm. To do so, we had to make a connected graph of all points on walls in the map that could be reached from other walls. We created a data structure, which we call a SparseIntersectMap, to hold this information. It contains x, y, and angle coordinates, mapped to other x, y, angle coordinates, with distances. It also contains the means to find the correct bin for an arbitrary x, y, and angle value, with a specific granularity. This allows us to take an approximate location, reducing the storage costs to a manageable number from the unimaginable cost of storing connections at every pixel.

Another class is used to create this graph, casting rays from each bin, getting results, and storing them in the SparseIntersectMap. Another shortcut is taken here – once a location is reachable from another bin, we store the back-connection as well, avoiding casting again when we reach that bin.

Finally, once we have the graph, a standard A* algorithm can be used to find the paths. This is the most standard part of the process.

We found that there were some problems with this approach. Casting at large angles could cause bounces between obstacles that were almost touching, leading to paths between walls that were not actually passable. Therefore, we cast only at angles that are somewhat closer to the normal of the wall. Additionally, ray casting from within an object causes the cast to ignore that object, so we ensure that all casts are done slightly inside the wall, avoiding ignoring any other objects that may be touching the wall.

The result is a fairly decent pathfinding system. It still could use more tweaks: it sometimes finds paths that go very close to a wall, where the player will actually hit the wall instead of getting past. This is somewhat less of a problem than it might seem at first – even real players cannot always calculate their trajectories properly to get there on the first jump. Nonetheless, we are looking into ways to reduce this problem.

We have also added a non-standard extra weighting to the A* algorithm – we found that paths would often be placed in such a way that the player could get stuck jumping from one wall to another, always calculating a new path that led back to the old location before continuing. Therefore, we put weights such that the most recent old location is less desirable. This has reduced this problem.

I’ll keep posting as things progress – the next step will be to create a finite state machine system, allowing us to add some more strategy to our reactions, following an overall ‘personality’ or ‘current objective.’

Advertisements

~ by greywhind on March 30, 2011.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: