Currently looking researching new techniques for pathfinding other than optimised A* and/or derivatives based on grid/connected graph systems, and having found plenty of reference material for pathfinding algorithms I''ve realised I haven''t come across any for generating good walkspaces (or whatever general term is used). So many of these articles assume you use a grid based walkspace, all fine and dandy, there are many ways of creating them easily. The problem with grid based walkspaces is that they take more time for A* to search across over large distances or through complex obstacles, and they also take up more memory. I''ve seen some interesting articles talking about removing some of the large redundancies in the walkspaces and generating large quad based free sectors using edge cells , for example, but none of them go into detail on the generation and optimisation techiniques/code to do this. I had a think about how some of these would be done, and found that it can be rather complex (recursive decomposition algorithms, but sticking to optimised quads etc). Is this a reason why noone talks about it? If they do, can anyone point me to a good reference on the subject or discuss here?

I''m not entirely sure I understand what you mean by ''walkspaces'', but I at least think I do. I am assuming that you mean walkspaces to be the graph that you are performing your pathfinding through. If that is the case, then I have been dealing with the same problem recently. If not, then I apologize, and you can disgregard this response.

As you said, the grid based approach has problems. The biggest is memory consumption. Also, doesn''t work well if you have irregularly shaped objects on the map. If your entities are restricted to grid squares, like a traditional 2d isometric game, then this isn''t a problem. If you allow them to roam freely, then the grid approach becomes innacurate unless you make your grid spacing so fine that it becomes unreasonable.

I agree with you that it is a topic that isn''t discussed often. I had a friend who spent a summer at Honeywell and worked on a project where he had to do this. He did some research, and there is a lot about it in the robotics field. They actually get a bit more complex and get into something called configuration space, which is basically searching through all configurations the entity could exist in. This is essential, for example, if you want to see if a long truck could squeeze around a tight corner without hitting the wall. In practice, if you are dealing with objects that aren''t very long, you don''t need to get this detailed.

The first article I read that even mentioned this was in Game Programming Gems volume 1, called The Basics of A* or something. It mentions a few ways to do this, such as a grid based approach, or a quadtree based approach (which would be similar to the techniques you discussed, taking advantage of contiguos areas in the terrain.)

The approach I am currently using, which is mentioned breifely in that article is (roughly) as follows:
1. Determine the width of the moving object.
2. Find a bounding polygon for every object on the map.
3. Take each line segment in these bounding polygons and extend its length by width/2 (this will be so the object doesn''t pass through the corner of an object.)
4. Make a node in your walkspace for each end of each of these segments.
5. Using some sort of intersection test, check every node against every other node to see if it can ''see'' it without passing through any of the segments. If it can, add a connection in the walkspace graph.
6. Use your pathfinding algorithm (such as A*) to find the path through this walkspace.

This algorithm works pretty well, but has some inneficiencies. Generating this walkspace can take some time. If your environment is primarily static, though, you don''t have to regenerate the entire walkspace every time you do the search. You could get away with simply adding and removing objects from the walkspace as they move around. Adding an object is simple - it takes O(n) time, because you simply have to check line of sight with every other node. Removing an object, I believe, would be O(n^2), because you would have to re check every node for line of sight against other nodes. So in highly dynamic environments, storing the map wouldn''t be too efficient. I haven''t put much thought into it, but there may be ways to make removal more efficient.

The technique I am currently using is actually a bit of a variation on this. Basically, I am simply generating the areas of the walkspace that will be relevant to the search. I am almost finished implementing it, but when I finish I may benchmark it against the straightforward version. If I have some time tomorrow, I''ll post what I have changed for my algorithm.

Yeah, this is what I mean by ''walkspaces''!

Nice idea... reminds me of Voroshnoi diagrams (if I remember how it''s spelt!) which I did in Robotics back at Uni, by locating the loci between the objects bounding vertices and creating a highway by linking up these loci ''nodes''.

We have a similar system, though hand defined by our level builders in another project. Although it''s fast, it deosn''t really allow the AI''s to move totally freely within the space, and you''ll find you start getting problems with multiple AI''s using the same line of movement. Trying to get away from this too!

The last project I worked on used a grid based system, and obviously, I found the A* to be slow when long distances are involved. But I also want a free space for the AI''s to walk around and take cover etc. I was thinking of using a pre-built (using flood-fill) quad tree based walkspace for static objects (walls, trees etc) and perhaps using potential fields for any dynamic, moveable objects. The last thing I want to do is start re-calculating the quad tree''s real-time coz a truck or car is movnig across it!!!!
I''ve done some potential field stuff in robotics before, and it seems quite useful. Say the AI has calculated it''s path, and is moving using bezier curves (for more realistic movement). If a truck is then to move across the AI''s path (you wouldn''t have been able to take it into account during the AI''s A*), you can simply manipulate the control points for that part of the bezier curve and ''pull'' the path behind the truck.
This way, anything that''s moving forward will have a strong potential pushing AI''s in the opposite direction to which it is travelling.
Do you think this''ll work well?

Yeah, what you are describing sound very much like the approach taken for the QuakeBot. The thing about it is that the QuakeBot makes a full 3D analysis of the map (not just walking space) which is pretty intensive, *especially* when you start having to calculate the reachability (is that a word) of various volumes (that''s so that a bot knows he can jump from one point to another)...

another nice approach was suggested in a brilliant article on Gamasutra.
Personally I prefer that approach, although it has a few limitations.
Particularly, how do you deal with objects that have very different bounding box sizes (say, your game has tanks AND infantry). Do you generate a different graph for each bounding box type ? Not very efficient...

The solution I have been thinking about (unfortunately, I have more pressing things to do right now, so I dont have time to experiment) would be some sort of tesselation approach.
Start to analyze your map with the largest bounding box available, then as you encounter areas that you cant move to, try smaller and smaller boxes (say half the size each time) that can go there, until you dont have any box that can, in which case the area is "unreachable".
I know it''s a bit sketchy, but it''s really just an extension on what is described in the article above, that would accomodate for variable size bounding boxes.

As for dynamic path finding in such an environment, that''s an entire ballgame altogether

---

Sancte Isidore ora pro nobis !

It would be nice if everyone picked a standard for this, kind of the way (i assume) BSPs became for graphics/maps

The way i saw mentioned was the whole flood fill thing. You end up with a large grid (that can adjust a bit for variations in the floor - flood by having some invisible bot actually try to navigate). Then you compress the cubes by removing all the ones that are touched by it''s peers on all 6 faces. A guy in Sweden (i think) did a master''s thesis on this topic. i could find the paper if interested, but it sounds like you''ve already got some good pointers to this

For navigation with diff sized units, i don''t know. i always just said "person X requires 2x standard path" and saw if two side-by-side paths existed (also good for checking things you have to crouch for). Computing different walking paths is no fun

For navigation in crowded areas, what a pain. It really bummed me out in Baldur''s Gate when you had to reach a door and lots of NPCs were coming in and out and around it. i''ve seen some ways around that, like using flocking (somehow), having NPCs have a minimum distance square/hull (so if you get w/i 1m of them they move away), being able to push NPCs and turn taking (like in networks - if a door is blocked, each person picks a # b/w 1 and 10 and waits that # of seconds before trying to cross the bottleneck)

Something else to consider is the idea of supersumption. i believe the robot people came up with that one. Your higher-level brain gives vague commands like "move from here to the next room". A lower level calculates a path or series of path segments (which in fairness can sometimes be done with just ray traces; isn''t this how humans do it?) and an even lower level calculates how to move small increments in it. Which is to say, one part of you says "let''s go from Paris to Lyon". Another part looks at a road map and picks the roads to take. A more tactical part knows you want to go straight down the highway but there''s a car in your way so it decides to move left, pass the car and then move right again. In other words, it "patches" your plan to do obstacle avoidance

Hope that helps

-baylor

Thanks for the replies!!

ahw, the way I''m looking at doing it is based on the ideas from that article in Gamasutra. You could use different sized units, as long as the sectors and portals could fit them.

Thing is, I don''t want to get into too deep and comlpex an algorithm, because the main issue I''m looking at is the speed and memory issue of using a fully defined grib-based system. I''ve worked on the Gamecube where speed and memory were an issue, and saw frame rates drop because of the A*.....

We just get back to that whole thing huh? Fast but more memory, or slow and less memory.... =P

Baylor, do you have that link to the thesis? It would be cool to take a look at it! Any information is good information! =)