Hi, I'm working on pathfinding for a game (in A*). My question is how do you actually put it into a level? In tile based games the implimentation seems trivial enough, but in say a first person shooter how would you go about dividing the play area up into a grid? I'd asume you can prebake an array of nodes and update as obsticles are made/destroyed, but how do you do this? Is a grid created by artists who are modelling the level, or is an algorithm ran over the level when it's completed? I keep thinking of problems that could arise with an algorithm, like cells that are half walkable and half not (like one that sits on a banister). If all you're doing is dividing the world up into cells of dimensions 1/(world width), stuff like this seems to be very possible, though perhaps if you cast a ray at each cell corner and checked for absurd height differences this would help avoid the problem?

Hi there, I've implemented pathfinding in a 3D world. I used a home-grown method but the underlying concepts are similar. As you mentioned in a tile-based map it's a trivial setup. The procedure in a 3D world is to drop nodes at 'critical' junctures in the map (this is done by a human). These can be thought of as the equivalent as your 'tiles' in a 2d game.

You then must compile information pertinent to your algorithm in order for it to function properly, e.g. with A* you may 'weight' one move against another based on distance, how 'difficult' it is to get from A->B, etc.

In my implementation I do a line-of-sight test and build a series of sparse connectivity matrices (most entries are 0 and are not included in the matrix). You can use these matrices to determine where you can get from one node to another and how many 'moves' it will take (you can make the next move without having to have calculated the entire path, thus saving time).

Quote:
I'd asume you can prebake an array of nodes and update as obsticles

In a typical implementation of a 3D first person shooter, when an obstacle gets in the way they typically just employ the 'bump and slide' algorithm for finding a way around the obstacle (e.g. a massive crate falls in the way). The A* (or whatever pathing algorithm) just gets the bot to the right part of the world, and isn't really used for finer movements e.g. around small obstacles.

For a 2d game like starcraft, the grid is obvious.
For a 3d game, the grid isn't so obvious. Some games take the approach of A* over preset nodes. Those nodes are just a series of hand
placed waypoints in the level.
Other more complicated techinques I've seen involve running random agents over the player walkable area and generating nodes automatically.
In either case, the nodes aren't usually a grid in any way shape or form, beacause you don't need a grid to describe all the locations of interest a npc might want to walk to.

The most useful/easy(usage not implementation) techique I've seen is a navigation mesh. Where you just draw out another mesh over all the walkable floor,
and do some processing on that to get your navigation info. This happens in O(n^2) space, but gives you O(1) lookup of pathing info.

[Edited by - KulSeran on April 11, 2008 1:25:12 PM]

First of all, it doesnt have to be a grid. Polygonal navmesh for the win. There is also the point-of-visibility approach.

Once you've grasped these concepts, then there are many ways to generate your navigational graph from the level data. As usual I will recommend the article "Improving on Near-Optimality: More Techniques for Building Navigation Mesh" in the book "Ai game programming wisdom 3".

edit: I just got my copy, and there are also several articles on the subject in the new AI game programming wisdom 4.

[Edited by - Steadtler on April 11, 2008 3:13:47 PM]

thanks for the replies, I've opened myself up to new ideas for how to impliment my pathfinding, but this has left me with the problem of finding information on these ideas.

I looked up steering behaviours and found a few papers by a guy called Craig Reynolds.

However when looking for stuff on polygonal navmeshes everything points to these AI programming wisdom books and, as a poor student, I can't afford to shell out £30 for them (and for some reason the university library has all five copies of each on loan just now :/ ).

One of the reasons I'm researching this is for a paper I have to write (thought I'd just get that out of the way to avoid any confusion). I wanted to write the paper on pathfinding in games, the different methods used, problems and limitations of the methods, and the latest research on new techniques.

Additionally however I'm also looking to write a pathfinding algorithm for a project myself and a few friends are looking on, so the two tasks are sort of merging...

I thought A* is a fairly standard technique, so I've talked abou that, and steering behaviours. Now I'd like to talk about polygonal nav meshes and maybe fixed way points too, but these seeem to be harder to find papers or reputable webpages on. Most of what I've found seems to end in dead links :/

Quote: Original post by Winegums
I thought A* is a fairly standard technique, so I've talked about that, and steering behaviours. Now I'd like to talk about polygonal nav meshes and maybe fixed way points too, but these seeem to be harder to find papers or reputable webpages on. Most of what I've found seems to end in dead links :/

These aren't separate methods - polygonal meshes or waypoints (often pretty much the same thing, in the Delaunay/Voronoi type of way) just provide the nodes which A* or a similar algorithm would run upon. The search method and the world representation are largely independent.

Sadly it's going to be a bit hard to write your paper on the latest techniques if you can't get the AI Wisdom books, as I think they are where most of the newer techniques and approaches appear first.

You aint kidding on the AI Wisdom books. AI Wisdom 4 had 12 separate entries in the pathfinding section alone. It seems like every installment has something new on auto-generating and auto-updating nav meshes. That seems to be where the top stuff is.

Hi, so I got a hold of AI wisdom 1 and 2 and somehow got this paper from a link on the forum:

http://www.cs.ualberta.ca/~mburo/ps/tra.pdf


I have a couple of questions really...

i) In the above paper it's implied that you generate triangles from drawing lines from the corners of where line segments meet (i.e. the corners of geometry). how do you decide what corners to draw lines to? I guess you could los test each corner with each other corner (which seems slow), and then do another test for intersecting with existing triangles (again, slow), but this seems....slow. Is there a faster way of doing it? I couldn't really tell from the paper.


ii) I'm planning on developing a game where the environmental obstructions such as desks/cars/chairs/whatevers may move and, despite all the research, I'm not sure what methods are ideal for dynamic environments. It's not so much the algorithm for traversing the node list that I'm concerned with, as it is the method of maintaining and updating the list itself. the game would play in 3d (with stairs and such) should that make a difference. I'm planning on testing a few ideas anyway, but would appreciate any prods in the right direction, or methods to avoid outright.

Quote: Original post by Winegums
I have a couple of questions really...

i) In the above paper it's implied that you generate triangles from drawing lines from the corners of where line segments meet (i.e. the corners of geometry). how do you decide what corners to draw lines to? I guess you could los test each corner with each other corner (which seems slow), and then do another test for intersecting with existing triangles (again, slow), but this seems....slow. Is there a faster way of doing it? I couldn't really tell from the paper.

It probably doesn't matter. You do this processing offline so speed is less of an issue. Obviously there are ways of speeding up spatial database queries (eg. quadtrees/octtrees are popular) but it's not a great issue.

You also wouldn't tend to do it with all triangles, just relevant ones (eg. invisible collision geometry placed specifically, or just the walkable triangles, etc.)

Quote: ii) I'm planning on developing a game where the environmental obstructions such as desks/cars/chairs/whatevers may move and, despite all the research, I'm not sure what methods are ideal for dynamic environments. It's not so much the algorithm for traversing the node list that I'm concerned with, as it is the method of maintaining and updating the list itself. the game would play in 3d (with stairs and such) should that make a difference. I'm planning on testing a few ideas anyway, but would appreciate any prods in the right direction, or methods to avoid outright.

It's common to try and avoid changing the underlying nodes, treating the dynamic aspects as things that can switch nodes on or off, alter their traversal costs, or which can be implemented at the steering level rather than the pathing level.