News Developer Blog: Making the AI Work

http://www.bit-tech.net/blog/2010/08/11/developer-blog-making-the-ai-work/

 

Cool - this is exactly how I did my pathfinding in my final year degree project! It was a simulator for people evacuating a building to measure bottle-necks in floorplan design... in other words the closest I could get to writing a game for a degree project.

Looks like a very similar method - take corner of each object, pushed out by half width of a 'person' then build net of possible next corners.... then use the net in A*

 

Navigating by corners is a good idea, but how does it improve to just using smaller size squares. Surely the computer can calculate the least amount of squares to the destination?

With cpu's getting more cores and even virtual cores, is it useful for the AI-npc's to have one core each in such games?

How far are we off having the AI seeing in real time and analysing what he sees, in 3d for instance.

Does your game has more complex geometry like windows or stairs etc? And can the visuals be tweaked to other color-schemes? The default could get old pretty fast, and as bit-tech said in beta-testing, it wasn't really that readable.

Sorry for the bombardment of questions, just got really interested

 

I know that Frozen Synapse at least includes obstacles of different heights, allowing for window gaps and cover. You can see them in the pictures above - light blue is a low height object, which players are exposed if they stand behind unless they crouch.

 

so you are simply using a waypoint based system, albeit the waypoint's are getting auto generated. Grid-based pathfinding is the least effort and the path quality is excellent.

I'm more than sure you would have had better results with a grid-based approach using an optimized A* (priority queue based), theta A* or fringe search.

Seeing as you can now navigate via corners, if you wish to move to a location that isn't a corner, I'm assuming you first have to find the nearest corner, navigate to it and then move to the final location? That is an awful amount of unnecessary work and your path lengths will end up being grossly suboptimal.

you also say that using a grid to approximate the game environment is really inaccurate, that's simply not true, short of using a near-optimal navigation mesh, grid based pathfinding offers nearly the same amount of accuracy, with the added benefit that grid based navigational map updates cost O(1) where as with a navigational mesh this will trigger a whole new subdivision and recombination routine.

Pretty much most of the modern pathfinding research is based upon grid-based navigational maps. I can link you to several papers that might prove useful in the future if you are interested.

 

Hi Coldon.

"your path lengths will end up being grossly suboptimal"

This approach produces 100% optimal path lengths in every single situation.

I'm willing to accept that this approach might not be the fastest, however I'm not entirely sure how even an adjusted-grid-based system (which is required as FS' levels are vector, not grid based) would produce the optimal path without an expensive post-step to work out which parts of the grid path could be turned into diagonal movement.

I agree that the recalculation of the nav-mesh is expensive, but FS only ever has to regenerate once per turn and the recalculation takes < 1 second so it's not really a problem. In general, if I find a solution which makes 100% perfect paths in an acceptable time I don't feel the need to further optimise.

 

To what are you comparing your path length optimality? If you do calculate the paths according to the nearest corner and then do the initial/final movement step to/from it, I cannot see how your paths would be optimal, perhaps you will get at best within 90% optimality but not fully optimal.

even if you level data is vector based a single grid map of the level can be generated and scaled as needed, now I'm not saying you should use grid maps, if your level data isn't dynamic then navmeshes are the way to go. Its jsut I have yet to see a single game using navmeshes in a dynamic environment, relic uses grid maps in DOW and COH.

<1 is a bit worrying, in your case, it seems the game is turn based so that's okay, but if it was real time, that time is unacceptable, for example bioware buts a 3ms constraint on pathfinding searches, so having a single component taking a massive amount of time is usually unacceptable.

I guess I am nitpicking a bit, and at the end of the day, your technique works and that's whats important.

 

Can you give me a situation where you don't think it would produce an optimal result? Again - I am perfectly willing to accept I'm wrong on this one, but I haven't seen a single instance of a non-optimal route so far.

We are talking about the same meaning of "path length" yes - as in, the actual distance the unit has to travel on the path.

Ian

 

in the above example the green dot being the goal, the light blue path uses the closest corner, while the dark blue is the shortest path. Obviously the light blue section is a lot longer than the dark blue. What you can do in your algorithm is, as you explore a node (pop off open list), do a line of sight check to the goal and if its successful, then you have the final path.

So you will terminate the A* search not when the closest corner found but rather when a line of sight check passes. This again is all conjecture based on my understanding of how you are doing your pathfinding, i could be making a wrong assumption somewhere along the line.

 

Ah, I definitely didn't make this clear, and my apologies.

For my first step, I add the initial starting position (not a corner) as an actual node, as in I add it with all of the visible nav-nodes.

For the final step, I stop A* when I get to a node which can *see* the end node (not the closest to the end node)... is it possible that that may choose un-optimal result? I'll investigate.

 

no, that sounds perfectly solid, paths generated in that way should be optimal in regards to the navigational geometry present. Thanks for clearing that up! I was pretty sure that I was missing something

I think that for your current use, your selected algorithm is perfect. Though if you make the environment dynamic at a later stage, it may be necessary to use a different underlying navigational geometry.

Great work so far and best of luck in future. If you ever want to discuss pathfinding algorithms, give me a shout, I've spent the last 2 years researching realtime pathfinding in dynamic environments for my thesis.