Polygon soup - 3D pathfinding

Rambus · Post by **Rambus** » Wed Jul 09, 2008 2:47 am

I have been busy implementing 3d path finding for my games bots. I don't like the idea of having to place bot waypoints in the world editor just to achieve meaningful path finding so I have started implementing a 'flooding' algorithm. (described here: http://www.gamasutra.com/features/20020405/smith_01.htm )

I have heard that article referenced here on the forums, and I thought I would post a few screen shots of how my implementation turned out.

*note this below is in a 'debug mode', when doing it for a real map the cells would be much smaller and would produce a much more detailed graph.

start with an empty level

'flood' the level with cells

Cluster cells into sectors and remove the inards

from the cells derive the largest possible 'sectors'

Finds cells that touch other sectors, save them to make portals (toss the others away)

Where sectors meet, and it is possible for the bot to enter the next sector create a 'portal' between the two.

Only the final portal list (last picture) and the sector list (2nd last picture) are actually kept- the rest of the cells are tossed away.
Then the list of portals/sectors can be stored to a file for a bot to use later.

And then you are left with a small amount of data that can be used to easily run A* pathfinding- and now your bots can find their way through a maze

Large map example:

(sectors shown)

The portal/sector calculations are done as a pre-processing step when you save the .scene file in OgreMax.

I would love to hear some constructive comments.

dudeabot · Post by **dudeabot** » Wed Jul 09, 2008 4:15 am

really impressing!

congrats

Vectrex · Post by **Vectrex** » Wed Jul 09, 2008 6:32 am

groovy. I assume you'd need to be able to change the initial cell size to fit in the smallest area you want to be able to walk through?

Jaiza · Post by **Jaiza** » Wed Jul 09, 2008 6:49 am

Cool as!

volca · Post by **volca** » Wed Jul 09, 2008 9:14 am

Nice! I assume you could also do a sound propagation on the resulting structure, as lined out by Chris Carollo here:
http://www.gamasutra.com/features/gdcar ... arollo.ppt

Chris Jones · Post by **Chris Jones** » Wed Jul 09, 2008 10:41 am

i can't see the images

Rambus · Post by **Rambus** » Wed Jul 09, 2008 5:41 pm

@Chris- might have just been a server hiccup, they seem to be working fine now.

@Volca- Yes this structure is ideal for sound propagation. Thanks for sharing the link, I hadn't seen that power point before. I'll definitely play with the concept in the near future.

@Vectrex- The ideal cell size is one quarter the size of your player (width/depth wise. Full height). This helps deal with small non axis-aligned corridors.
You pass my command line program a .scene file path, width of cell, height of cell, position (x/y/z) of starting cell and then any special flags required (like dump results to a xml file, etc).

Chris Jones · Post by **Chris Jones** » Wed Jul 09, 2008 5:46 pm

i still can't see them. If i open them in their own tab, i get a page load error, network timeout.

KungFooMasta · Post by **KungFooMasta** » Wed Jul 09, 2008 5:47 pm

Interesting concept, but how does this work when you have units of different sizes? (ie a cat can walk under the park bench but a person has to walk around it)

Also, how does this work with varying elevations? The article mentioned a spiral staircase, is this something that can be handled by the algorithm?

[edit] I see the images fine.. [/edit]

Rambus · Post by **Rambus** » Wed Jul 09, 2008 6:00 pm

@Chris-
I mirrored them here:
http://www.g0dsoft.net/forum/flood1.jpg
http://www.g0dsoft.net/forum/flood2.jpg
http://www.g0dsoft.net/forum/flood2_2.jpg
http://www.g0dsoft.net/forum/flood3.jpg
http://www.g0dsoft.net/forum/flood2_3.jpg
http://www.g0dsoft.net/forum/flood4.jpg

@KungFooMasta-
This was not shown in my images but yes the method can handle elevations fine. If it is a small, meaningless elevation (stairs) is encountered then that elevation is just added to the sector (offset for the cell, but during sector discovery the height of a sector can grow). If it is a cliff, and the player can jump off then a one way path is made- so that the portal doesn't go both ways. This allows the AI to take advantage of elevations with out having to worry about them getting stuck at the wrong end of a cliff.
This method takes virtual 'player steps' to decide if the next cell is available. This allows me to know if the stairs are traversable by a given set of rules or not.

As for the cat problem- I believe you would need to compute a separate graph for each character. You could also compute the highest detailed graph and then encode information about who can fit through a given portal. I'm using a standard sized characters for my project so I haven't given this much thought

Evak · Post by **Evak** » Wed Jul 09, 2008 6:10 pm

Reminds me a bit of the velocity engine AI we used in Motorsiege. Only in that we used 3dsmax as a level editor and created floormap meshes in max too. You just cut out the floor around static collision and the AI would never go there. Had flags for jump up and jump down so the AI knew it could navigate different levels, and you could use vertex colours to change basic behaviour of the AI so that it would try and avoid dangerous areas.

The AI picked waypoints dynamicly by intersecting edges and doing something a bit like a reverse LOD if needed.

Using the mesh created floorplan meant artists could optimize the mesh rather than having a huge grid of cells. This was back in Xbox and PS2 days when the CPU was a limiting factor. But it worked really well.

Sometimes troubleshooting could be a pain, since inexperience artists might leave verts between floormaps not overlapping 100% and the AI couldn't pass broken edges.

I really liked that AI because you could simplify collisions in a racing game with the holes around static meshes inset a little the AI never tried to pass through a wall and would rarely collide with a static scene object unless it was thrown against something through concussion or being pushed by another player. (was a vehicle combat game).

Chris Jones · Post by **Chris Jones** » Wed Jul 09, 2008 6:32 pm

thanks, those links works fine.

Rambus · Post by **Rambus** » Wed Jul 09, 2008 8:10 pm

I had originally planned to put in 'hints' for AI in the level its self. In the form of waypoints or sectors (as pictured above, only manually placed) but as you mentioned the problem is that these need to be manually tweaked and can suffer from poor placement (in your example inexperienced artists did it wrong). The other major issue is maintainability- if you want to make a structural change to the scene you have to adjust your hints.

In the end after my program has run you are left with a path finding graph that is automatically generated, uniformly with no unexpected placements. Also it is very light in memory and easy on the cpu.

Rambus · Post by **Rambus** » Wed Jul 09, 2008 10:54 pm

I did a few more tests for everyone to see how the program handles more complex levels.

(These levels were done in 'detailed' mode, like a real level would be)

Sector view, curves create needless sectors. I'm going to look at merging insignificant cells/sectors into their closest neighbor. Alternatively I could search for a more complex convex shape.

A three tier level filled with detailed cells. (Approx 1s runtime)

Sectors derived from the above image... sorry for the strange colouring- It was supposed to make things easier

KungFooMasta · Post by **KungFooMasta** » Thu Jul 10, 2008 12:37 am

demo!

Nauk · Post by **Nauk** » Thu Jul 10, 2008 1:23 am

This looks very interesting, actually could be quite useful for my project, thanks for sharing

KungFooMasta · Post by **KungFooMasta** » Thu Jul 10, 2008 10:10 pm

How do you determine if a cell is within a sector?

I imagine the first pass is generating a list of cells, and then there is a second pass that iterates through the cells and creates sectors?

Rambus · Post by **Rambus** » Thu Jul 10, 2008 10:26 pm

You're correct, I do three passes in total. The second pass finds sectors from a ugly list of cells. It does this by picking the last cell in the list, using that cell data to spiral out radially until it has made the biggest rectangle it can (Greedy, biased). Repeat until there are no 'unused' cells in the cell list.

Each cell has a position, and 4 pointers to its neighboring cells (0 for no cell).

KungFooMasta · Post by **KungFooMasta** » Fri Jul 11, 2008 12:14 am

Thanks for the info, it makes sense. I'm still not understanding how cell discovery and height comes into play. For example, would this algorithm be useful in a scuba diving game, on the ocean floor? In your room, do you initially outline a 3d volume of space, and then check each cell to see if its able to be occupied by your unit? Do you have any plans to share any code? (either way, thanks for giving hints and helping me understand

)

Rambus · Post by **Rambus** » Fri Jul 11, 2008 5:45 pm

My algorithm starts by placing a virtual version of my character at a given position (usually a spawn point). I do an initial ray cast to place him flush against the ground and then add that single occupiable cell to my "unprocessed list". I then check the four neighbors of that cell to see if a virtual player could step there with out being impeded/falling-climbing too much. I add the successful cells to the unprocessed list, and take my initial cell and put it in the processed list. repeat until the unprocessed list is empty.
The cells in my algorithm also store a position of the ground, and this can go up or down depending on if stairs or a ramp were encountered. When a sector is created from a list of related cells, it uses a axis aligned bounding box that encompass all these points (+ the width and height of each cell).

The main problem with releasing my code is that it has some ties to my engine and game logic. After a little searching I did how ever find a old project called GOOF that implemented a path finding system very *very* similar to this. I took a look at their code and it seems they are using some one elses modular/flexible path finding code.

http://www.ogre3d.org/wiki/index.php/Ga ... _Framework

I'm not sure if that code base will actually be easier to work from, if not feel free to ask more questions

Rambus · Post by **Rambus** » Mon Jul 14, 2008 10:20 pm

A few more pictures, now that I have A* running on my data.

Finding the way around a simple corner.

A bug not really talked about with the paper- In this case one way point goes far out of the way because of how the portals were created. This is lessoned by the use of interpolation but it would not be eliminated. I plan to use the portal information in conjunction with A* and a basic raycast model to develop bots that don't need to follow a splined path. This will help me deal with the the appearance of simple dynamic obstacles like players- with out any major overhead.

I'm sick of looking at A* for now- so you will have to wait to see how it solves that 'maze' level I made

dudeabot · Post by **dudeabot** » Tue Jul 15, 2008 12:49 am

i took a look on the GOOF, but looks like the path finding isnt avilable in the editor?

also nice work there

KungFooMasta · Post by **KungFooMasta** » Tue Jul 15, 2008 12:53 am

In the second screenshot, the path looks like it changes in elevation. Is this true, or just appearing that way? The ground looks flat, so it seems a little odd.

Rambus · Post by **Rambus** » Tue Jul 15, 2008 1:46 am

@KungFooMaster
Notice the little border around the edge of the pillar? the portal that has the minor elevation in it occurs because it includes a cell that is slightly raised but accessible on the border. The waypoints (verts of the lines) in the debug drawing I posted are simply the mid points of the portal aabb's. Because we are giving the bot a unobstructed path the elevation information in the waypoints is less important. (If he walks forward we know he will make it regardless of the minor elevation changes)

@dudeabot
http://sourceforge.net/projects/argorha/
Sorry- I meant the above project that builds on goof.

KungFooMasta · Post by **KungFooMasta** » Mon Oct 20, 2008 6:35 pm

Rambus, I'm not sure if you still visit the threads, but in case you do, I could use more hints.

The game we are working on is similar to warcraft 3. In wc3 you can find pockets of land within the woods, that may not be normally reachable. Trees can be chopped down, eaten, or regrown, and this will affect pathing.

In your approach you start with a known location, ie spawn point, and flood the map searching for traversable cells. I'm thinking that we will need to traverse all cells within the scene and process them that way. However I don't see how we can have stairs in this case. We don't use stairs, but I'm wondering if this iterative approach is a good route to take. Basically we can get the root scene node and get its AABB to outline the total area to process cells. For each cell, I would try to do a physx raycast downward, while filtering the collision so that it only hits shapes of the collision group I designate as the ground, which could be a terrain, plane, etc. If I hit the ground, then I can do an intersection query to see if my players capsule can fit within the cell and not collide with any other objects. Using this approach, I would have a predefined map with bools, and update all traversable cells to true.

Does this sound like it would work? I think wc3 must use something like this approach, or some derivate of polygon soup pathfinding. Any comments welcome.