Polygon soup - 3D pathfinding

A place to show off your latest screenshots and for people to comment on them. Only start a new thread here if you have some nice images to show off!
Rambus
Greenskin
Posts: 100
Joined: Tue Aug 01, 2006 6:50 am
Location: Canada
x 6
Contact:

Post by Rambus »

Hello KungFooMasta,

The method I described is ideal for static geometry.

The reason is can work for 'stairs' is because rather then simply checking if my player sphere can fit into a given cell, I'm checking to see if my player cell can move from one valid location to the next. Meaning it allows a certain level of elevation change (that of a step, or a small fall) with out complaining. You don't really gain enough information for a FPS style game if you don't do this directional step (you can jump down a small cliff, but can't jump back up etc).

I have not considered more then trivially traversable dynamic obstacles (objects that can easily be avoided with a simple raycast model).

For a RTS style game I would imagine there is a better method of computing the playing area. My method fails for your tree example because no sectors can be computed in initially 'tree'ed' areas, and further the sectors generated if you turned trees off at run time would be a totally different sector graph. I would recommend looking at some sort of a grid approach for storing pathfinding data (If your game world really is a 2d surface). Furthermore you can still run the pathfinding a* algorithm on this grid (think array) and get satisfying results!

I would recommend looking into alternatives for RTS representations.
Akinz
Gnoblar
Posts: 12
Joined: Thu Oct 23, 2008 12:59 am
Contact:

Creating Sectors?

Post by Akinz »

Hey Rambus,

I'm working with KungFooMasta on implementing this type of pathfinding solution for our project, and I was wondering if you could provide any clarification on how you went about creating sectors out of the cells?

I'm having trouble coming up with a solution that won't result in long skinny sectors instead of bigger rectangular sectors. :?

Any help would be greatly appreciated! :D
User avatar
KungFooMasta
OGRE Contributor
OGRE Contributor
Posts: 2087
Joined: Thu Mar 03, 2005 7:11 am
Location: WA, USA
x 16
Contact:

Post by KungFooMasta »

Just to clarify, we are taking the approach of a grid. The grid is just a 2d array, like this:

Code: Select all

std::vector< std::vector< Cell* > > cellMap;
We first do ray casts downward to check if there is land. If there is not land, or there is but it is sloped such that we cannot stand on it, NULL is placed into the map. Otherwise we create a Cell object. The cell object has properties that we set, but its not really relevant to our problem. (But I can outline for anybody interested :) )

So now we have a 2d array filled with NULL and non-NULL values. We want to iterate through the map and create sectors.

First question:

How do you store sectors? I can't think of anything good, just a simple list of sectors, since our implementation will involve adding and remove sectors during runtime. (trees regrown or chopped down) Did you store your sectors in a list?

Second question:

What is a good approach to creating Sectors? My first thought is to iterate column by column, row by row, and create sectors horizontally. Then in subsequent rows, we have to determine if a group of cells belongs to a previously created sector, and merge them in. Is there a better approach? (If anybody has ideas they are welcome!)
Creator of QuickGUI!
Zero
Halfling
Posts: 50
Joined: Mon Mar 10, 2008 12:08 am
Location: Stuttgart|Germany
x 1
Contact:

Post by Zero »

Hello,

First: Rambus you have done a very good work :D :D

I tried this to but I don`t find a solution how do you do that? I looked at Argoha, but this isn`t a good solution for Rpg`s I think. Because they use the AAB, but what when you are want to go in one building? I tried to find a solution by analysing the vertices. But this only work acceptable for the terrain.

@KungFooMasta: Your way with the downward ray cast. How do you know the size of the ray cast? Do you use a ühysic ray cast with an physic body?

I will consider further, may we all can find an solution :D :D

Sorry for my poor english

Zero
Last edited by Zero on Sat Oct 25, 2008 9:29 pm, edited 1 time in total.
Image
User avatar
KungFooMasta
OGRE Contributor
OGRE Contributor
Posts: 2087
Joined: Thu Mar 03, 2005 7:11 am
Location: WA, USA
x 16
Contact:

Post by KungFooMasta »

Your way with the downward ray cast. How do you know the size of the ray cast? Do you use a ühysic ray cast with an physic body?
Assuming I can get the dimensions of the scene (which I'm still working on, apparently Ogre's _getWorldAABB function is broken) you will know the dimensions and be able to determine how far you need to cast a ray to see if there is land. I use PhysX for my raycasting. This way I could have multiple terrains, bridges, or whatever, all using the same collision group, and they would be detected as land. The one issue with my method is that I can't generate pathmaps for land over land. These would be bridges over walkways, or stairs over walkable land, etc.
Creator of QuickGUI!
User avatar
syedhs
Silver Sponsor
Silver Sponsor
Posts: 2703
Joined: Mon Aug 29, 2005 3:24 pm
Location: Kuala Lumpur, Malaysia
x 51

Post by syedhs »

KungFooMasta wrote:
Your way with the downward ray cast. How do you know the size of the ray cast? Do you use a ühysic ray cast with an physic body?
Assuming I can get the dimensions of the scene (which I'm still working on, apparently Ogre's _getWorldAABB function is broken) you will know the dimensions and be able to determine how far you need to cast a ray to see if there is land.
getWorldAABB is not broken, because you are expecting the result it is not meant to be - okay I know what you mean, but broken is not the right word :wink:

However, you can still use getWorldAABB and the result is of course not the land size, but the box which contain all of the land vertices - which is good enough. You can then just loop thru the negative x,z until postive x,z a, do the raycast and do whatever you want with it.
A willow deeply scarred, somebody's broken heart
And a washed-out dream
They follow the pattern of the wind, ya' see
Cause they got no place to be
That's why I'm starting with me
User avatar
KungFooMasta
OGRE Contributor
OGRE Contributor
Posts: 2087
Joined: Thu Mar 03, 2005 7:11 am
Location: WA, USA
x 16
Contact:

Post by KungFooMasta »

I believe there is a bug in that _getWorldAABB only consider immediate children, such as attached objects and SceneNodes. My root scene node always returns 0 for size, because I have SceneNodes which are attached to SceneNodes which are children of Root. I can obviously see massive terrain and my entity on screen, but still the root node says size is zero. I believe the name is misleading, or functionality is not working. This is in 1.6 RC1.

My only hope for obtaining scene size is to follow Xavier's advice, which is to maintain my own AABB, and merge it with the derived AABB of every scene node that gets added to the scene. (Root SN does not consider children :!: )
Creator of QuickGUI!
Rambus
Greenskin
Posts: 100
Joined: Tue Aug 01, 2006 6:50 am
Location: Canada
x 6
Contact:

Post by Rambus »

@Akinz - My algorithm was a 'greedy' one. I selected a cell from my list of cells, and then expanded it in all four directions (taking the adjacent cells) adding it to a list.
Example: 0's are valid cells, X means no cell, 1 is a cell in a 'sector cell list'
0 0 0
0 1 X
0 0 0
Expand up
0 1 0
0 1 X
0 0 0
Expand right
we can't expand right because the middle cell is blocked by the X, we never run the expand right command again once this has been triggered
Expand left
1 1 0
1 1 X
0 0 0
Expand down
1 1 0
1 1 X
1 1 0
And continue Up, Left, Down (in some constant order) until each has been stopped by not being able to expand in a given direction.
That is, all the cells when expanding in a given direction must encounter a new unused valid cell, or an existing cell in the sector list.
Make sure to remove the cells from the unused cell list, and repeat with the new first cell in the list.
This could be optimized to get even fewer sectors by implementing some sort of a non greedy algorithm. Or you could do a post processing step that recombines sectors more optimally (If 3 sectors can be covered by two larger ones, etc).

@KungFooMasta's first post
First question:

Off the top of my head I don't remember (I'm not near my code right now). Sectors contain lists of portals. As for sectors, you need a fast method of lookup up what sector a given world position is in to make this scheme fast enough for real time A*. I used some sort of a spatial tree to speed up the look up.
A side note:
My cells all have a constant AABB + a dynamic world offset. I use this information to create a AABB the encompasses all the cells and their offsets into a sector (which I store, and use for the spatial tree look up).

Second question:
Check out my the first part of my reply.

@Zero - again my method for generating this portal/sector graph has been targeted for indoor scenes. It is possible to generate such a data structure for 'indoor' areas of your worlds triggered by some sort of spatial portal from terrain to building. I'm not sure If I understood your question correctly though, sorry!
User avatar
bibiteinfo
Gremlin
Posts: 197
Joined: Wed Apr 12, 2006 2:48 pm
Location: Montreal, Canada

Post by bibiteinfo »

Hey guys I missed this post. I'm the author of the argorha pathfinding. http://www.ogre3d.org/phpBB2/viewtopic. ... highlight= It has been downloaded over 4000 times on sourceforge!! :shock: It's really amazing to see a lot of people tried it! I've used the same article as Rambus and made some improvement over the article such as hierarchical sectors.

I think my pathfinding should work pretty well in an RPG style game.

It's not finished yet because all my tests were done on GOOF, which is a canceled project. All the design of my pathfinding is to be flexible and go in any engine. I'm interest in putting it in any one else engine. It could be Rambus engine, or Kungfoo game ; it seems to do what I need.


For the W3 example, what could be done with my pathfinding is to recalculate at runtime a sector of one higher level. I don't think the Rambus one is doing this yet, but it's done with hierarchical pathfinding.
Image
Zero
Halfling
Posts: 50
Joined: Mon Mar 10, 2008 12:08 am
Location: Stuttgart|Germany
x 1
Contact:

Post by Zero »

Hi bibiteinfo,

I think your are right that your pathfinding is good for RPG, but when I want to have Pathfinding in buildings?
Your Pathfinding is working with AAB`s but thats the problem when you want to use it in buildings, I think. At the moment I think the only solution is to use custom waypoints for the building, created by the leveldesigner or so on. Or may I try to generate a navigation mesh for the building?

Have you or someone else a better idea?

Zero
Image
User avatar
bibiteinfo
Gremlin
Posts: 197
Joined: Wed Apr 12, 2006 2:48 pm
Location: Montreal, Canada

Post by bibiteinfo »

Hi zero,

Well it's done for building too ;) I think it would work pretty well in building. It's a flood fill, so it's gonna find it's way inside the rooms. The structure is there to open the doors and so on, but I would need a test platform to code this part of "actions to take"!! :D
Image
Zero
Halfling
Posts: 50
Joined: Mon Mar 10, 2008 12:08 am
Location: Stuttgart|Germany
x 1
Contact:

Post by Zero »

Do you mean your pathfinding algorithm? Because I mean your algorithm^^
Image
User avatar
bibiteinfo
Gremlin
Posts: 197
Joined: Wed Apr 12, 2006 2:48 pm
Location: Montreal, Canada

Post by bibiteinfo »

Yep I mean my pathfinding algorithm!
Image
User avatar
SongOfTheWeave
Halfling
Posts: 49
Joined: Sat Dec 22, 2007 3:49 am
x 2

Post by SongOfTheWeave »

I implemented that paper a while back and this style of pathfinding is unnecessary (read: overkill) for an RTS game.

If the walkable area of your world is always a function on the x,z plane (or x,y if z is up) then there are simpler methods you can use (like... simply treating the world as a 2d grid/array/image that is either walkable or unwalkable). That way you can save it out as B&W image, easily visualize it, and have a simple constant time check to see if any given position is walkable.

The reason this technique is called the "polygon soup" technique, is because it can work for ANY arbitrary geometry. But if you can make some assumptions about your geometry like I mentioned above, you can do it better/faster.

I use this technique because my walkable region is not a function. I have buildings that you can walk up stairs and be standing directly overtop another spot that is walkable too. For every (x,z) point there may be more than one y that is a legal walkable location.

As the OP mentioned, there are some issues that are unresolved in the article:

1) It's not very bloody easy to take a list of portals that defines a "path" and turn it into a REAL linear path that you could make an agent walk. I sill don't have a great (and fast) way of doing this. I end up casting a load of rays and writing more code than I wrote to do the A* search on the sector/portal data.

2) Related to the above, if you're just approximating the location of your portal as the center of the portal for the A* search... that's... bad. Imagine a very long portal (which often occurs) and then a small portal next to it 90 degrees rotated that goes into another sector which has a portal back into the sector on the other side of the very long portal.

If you try to path from the first sector, through the very large portal into the sector on the other side, there are a bunch of points close to the edge with the smaller portals where it will choose to go around the long portal, through the small doors and back in behind the long portal if you're using the center of the portal as the "estimate" of the portal's location.

Icky.

So, yeah, this technique sounds really awesome, but it's the opposite of easy and isn't the Best Solution Ever For Everything (tm). Examine your needs first, of course. And if anyone has a good solution to the two problems I mention above, I'm eager to hear them!

This is a smallish area in my project:
Image

[edit] P.S. I do NOT recommend doing a visualisation as large as the one pictured above using WireBoundingBox as I did... it grinds to a halt. Probably due to inefficient batching. Which is not suprising considering there's probably close to 10,000 sectors and portals in that image.
Akinz
Gnoblar
Posts: 12
Joined: Thu Oct 23, 2008 12:59 am
Contact:

Post by Akinz »

KungFoo and I have finished implementing our first revision of pathfinding based off this paper with a bunch of tweaks for our RTS-style project.

Some main differences are that we don't support multiple levels of terrain (multiple y values for a x,z), and instead of recursively populating the grid through a flood-fill type procedure we ray cast onto each cell to determine certain properties (terrain exists, slope, height) to make up a grid representation of the map.

Since our environment has dynamic elements (buildings destroyed, trees consumed/regrown) we keep all the cell data for later use, but mark cells that are obstructed so that they do not get added to any sectors. We check for movement from each cell of the grid by comparing height change and checking for obstruction.

When a building is destroyed or a tree is consumed, the cell(s) underneath the object will become unobstructed and will notify all surrounding sectors to re-evaluate any existing portals and search for new ones.

Currently, each sector and portal keeps a list of cells that make it up. This way, when we have a unit requesting a path to a location, we can easily find what cell and sector the start and goal positions are in. We then do A* by passing in all cells that a portal in the current cell's sector leads to, continuing through all sectors until the goal sector is reached. This way, we are not passing in a generalized position for the portal, but a list of all cells making up that portal and A* chooses the best one to take.

There are also tons of optimization techniques that you can improve upon this process. Many optimizations I plan on implementing later include ideas from the hierarchical pathfinding paper bibiteinfo linked to. Refining the data structures and heuristics used by A* can also help.

By keeping all the cell data for each sector, you can find an abstract path from sectors to other sectors, and use A* on the individual cells of a sector as your unit enters that sector, to pathfind from border to border.

Anyway, these are solutions I have tried to implement to combat the types of problems you mentioned, however they are pretty customized for the type of game we are creating and our specific needs.
User avatar
SongOfTheWeave
Halfling
Posts: 49
Joined: Sat Dec 22, 2007 3:49 am
x 2

Post by SongOfTheWeave »

Akinz wrote:By keeping all the cell data for each sector, you can find an abstract path from sectors to other sectors, and use A* on the individual cells of a sector as your unit enters that sector, to pathfind from border to border.

Anyway, these are solutions I have tried to implement to combat the types of problems you mentioned, however they are pretty customized for the type of game we are creating and our specific needs.
How large are your level areas relative to the size of the smallest pathing unit you need? In other words, what resolution does your pathfinding data have to handle? I kinda ruled out being able to keep the cells around because I need resolution down to about .5 meters (to path through doors etc.) and my areas are on the order of hundreds of meters square. Which means that to cover an area 256 meters square with cells, I need 262,144 cells. Of course that's just a vague estimate, since not all the terrain is walkable or reachable, and it doesn't account for any buildings that have multiple stories. That many cells often compresses down to 10,000 or so sectors and portals on a moderately complex level.

What benefits are you trying to achieve using this technique over a "walkmap" technique?

How many possibilities do you end up with each iteration of A* (on average) testing each cell of each adjacent portal? Does that technique seem to be working well?

Are your units pathing each frame/AI cycle or are you doing pathfind once, then move over many frames? If the latter, how do you alert units that have found a path that the pathing data has changed?
User avatar
KungFooMasta
OGRE Contributor
OGRE Contributor
Posts: 2087
Joined: Thu Mar 03, 2005 7:11 am
Location: WA, USA
x 16
Contact:

Post by KungFooMasta »

While we don't have very complex scenes to test against, I think our method could even be expanded to support land over land scenarios. (like spiral staircase, platforms over land, etc.) Right now we generate a pathmap against a specific collision group. So with our component based system, its possible to have multiple terrain, bridges linking terrains, or mesh made ground included in our pathmaps. (assuming they are all tied to the collision group used to generate the pathmap) For land over land scenarios, we would just have to enforce that the upper portions of land are on another collision group, create a separate path map for this group, and link sectors together. This is my theory anyway, its not needed for our game, but I'd be interested to see if this provides a good automated method for 3d pathfinding in any level. In our case, the goal is to not require level designers to manually playce way points or navigation meshes.

From viewing Akinz solution is seems that issue 2 as raised above does not exist for us. As for 1, we'll need to test more complex scenes to see how we perform. But opposing the remark about "this isn't the Best Solution Ever For Everything (tm)", I'm more optimistic.
Creator of QuickGUI!
User avatar
SongOfTheWeave
Halfling
Posts: 49
Joined: Sat Dec 22, 2007 3:49 am
x 2

Post by SongOfTheWeave »

KungFooMasta wrote:From viewing Akinz solution is seems that issue 2 as raised above does not exist for us. As for 1, we'll need to test more complex scenes to see how we perform. But opposing the remark about "this isn't the Best Solution Ever For Everything (tm)", I'm more optimistic.
The way he's doing it should get around #1 too.

The logic behind my trademarked remark is that you're using a lot more memory with this solution, especially keeping the cells, than a walkmap solution. Of course, the walkmap means a spot is either walkable or not, so it can't represent say... cliffs, that you can jump off, but not get back up (Of course, cliffs so tall that you'd die if you fell off, you'd want the AI to treat as non-walkable).

[Edit] However it's possible that the sector/portal technique would yield faster pathfinding performance than a simple walkmap by virtue of having fewer verticies for A* to solve through.
Post Reply