Just a little idea I had... Say you''ve got a portal-based map. The world geometry can be broken down into pieces; each piece encompasses a convex volume. The volumes are joined together by way of portals - planar polygons. Our AI agent starts within one of those volumes, and needs to reach a different volume. So he uses the A* algorithm to build a path through the node network. Each node in the network represents one of the convex volumes. The links between the nodes represent portals, and are stored as such. One of the first steps in the A* loop is to determine whether a node is usable or not. This can be done using the portal, I believe; you take the agent''s bounding volume, and project it into a plane; you then test the result against the portal polygon. If the portal can completely enclose the bounding volume, the portal is passable and so the volume it connects to is added to the open list. So far so regular. But what if we were to store extra information with the portals - such as their height from the ground? The resulting path could then include special actions - jump/climb to reach a higher placed portal, or crouch to crawl through a tunnel. What do you think? Has this been done before to any degree of success?

I've found that this type of scheme allows for all kinds of cheap behavior modifiers. You can also have a cell keep a list of pointers or IDs to all edges that pass through it, and notify those edges when certain events happen inside the cell, like a hostile creature enters the room, one of the characters friends was killed there recently, some hot babe with large boobs and no morals is laying in a lounge chair drinking copious quantities of tequila, all of these things can be used to affect an edge's cost.

You could also store instructions for passage in a link. More than just whether to jump, whether to climb, you can store higher level information. Suppose you have a door that is locked, the portal will keep a list of instructions for passing it:

retrieve red key
come back
unlock door
step back
pull door open
pass

The character could then query it's logic system for 'retrieve red key', and hopefully the character will have logic for that and be able to determine how far they would have to travel to get the red key and come back, and add that to the cost of the edge. You can store more specific information like which animations to use, where the keyhole and door handles are in order to help drive your animations, etc. If the agent doesnt know enough, for instance, hasnt found the red key yet, you could assign a really high cost.

You can have edges to things other than actual portals as well. You could, for instance, have an edge that goes to a motorcycle, that would have information on how to mount and drive it, how fast it will increase your speed between other waypoints, etc. that will help the AI decide whether it is best to take the straightest route across the map by foot, or run back and get the motorcycle.

You would probably want to make it hierarchical. Besides the main edges between portals, you can have a number of waypoints inside of each cell to help navigate through it. You can use the same A* algorithm when you are in the cell to find your way around in it, and you only figure the lower level paths for the cell that the character is in, and use the higher level portal-portal paths for traversing through other cells.

You can have a bounding sphere or bounding box associated with these waypoints that determine their areas of influence; to get from point A to point B within a cell, find the closest waypoint to point A, and the closest waypoint to point B and use your A* or other algorithm to find the best path between those points based on some kind of cell map or weights that are generated offline and modified by dynamic objects to affect the cost of moving between each point.

Peace

[edited by - krippy2k on February 24, 2004 5:13:59 PM]

Wow, those are some really neat ideas, especially the ''portal prerequisite'' get-the-red-key stuff.

I guess it makes much more sense to work with volumes than with points/edges when looking at things like ''can I collect ammo while on my way to the target'' and so on. If there''s an ammo entity within a given cell (i.e. the collision detection system gives it to us), the pathfinder can take that into account - I initially thought that was a modification to the heuristic function, but now I''m not so sure. How do you influence a path to go ''via'' a particular cell?

It could also be extended for map learning, I think. An agent could keep a database of visited cells, with a small set of values with strategic information for each cell - health available, ammo available, "strategic worth" (if that can be assessed), danger level / number of enemies, etc. As cells are visited, that information gets updated.

With regards to going ''via'' a cell, perhaps it''s a question of creating the full path and then finding the simplest possible alteration to include the via node? Take a soldier, he could work something like this:

1) Prioritize goals. Let the primary goal be rendezvous with his squad at a given location; secondary/tertiary/etc goals include things like collecting health/ammo. The more damaged/low on ammo he is, the closer the respective goals get to becoming the primary goal. Say that when health drops below 25% then ''collect health'' becomes the primary goal, etc.
2) A target node is selected for the primary goal. This would be the rendezvous point; it could be the nearest cell with health packs/ammo in, or possibly the one with the best contents:distance ratio. (better to go a little further for more stuff than a little shorter for much less).
3) A path is built to the target node.
4) For each secondary goal, the path is ''grown'' - an A* search is conducted from each node in the path (I think this can be done through putting all nodes in the path on the open list). The limiting cost (i.e. the value at which it stops searching outwards) depends on the priority; if health is 75%, the search will not extend as far as if health were 50%. And so on.
5) Build a new path: from start node to ''via'' node, and then from ''via'' node to target node. (If there''s more than one ''via'' node I guess we''d need to build all possible paths, with the via nodes in all possible orders, and then pick the shortest path).

It seems a bit costly, especially finding the ''via'' nodes (and the final step of rebuilding the path), and there are probably many opportunities for optimization. I think it could probably be justified on a background thread - the soldier pauses for a moment to figure out where he''s going to go.

Pathfinding through portals has been done before... as has restricting the generation of successor nodes based on attributes of the agent performing the pathfinding. That''s not to say it''s not a good idea...

Timkin

Well, there goes my hopes of publishing ''Fine''s algorithm'' then. Any idea which games have used it? I''m curious as to how well it worked...

I *think* that some of the Red Storm games used that method, maybe even RavenShield. Not 100% positive though. Though I found the RvS AI to be pretty crappy, that might not be a good endorsement of the method, lol.

It is talked about briefly in AI Game Programming Wisdom 2, but they don''t say what games it was used in, the author was just described as somebody who develops tactical AI for games, and who works at CGF-AI. Incidentally, on the CGF-AI homepage you can see an example of how to modify A* to handle cover and concealment, so that instead of finding the shortest path through a room it will find the shortest path that provides adequate cover against a hostile in the room. www.cgf-ai.com

I have been using it in a game that I am working on (Reciprocity) for a while. It was one of the first pathfinding solutions I came up with, and it stuck.

Peace