Ok, im making a "Tower Defense" Game, where you have to build towers to kill your enemies before they reach certain place. I have a couple of questions and want also to post how i intend to implement my A* so that someone may correct a newb error that i might be doing, since this is my very first A* Implementation ;D I intend to use Navigation Mashes for Pathfinding but can't find good tutorials/books (that are free) on how to implement those!! neither how to use T.T anyone know where can i find those? Autogenerating will not be a lot easy since all levels will be made using a grind layout. Since too many agents will tend to use the same path, should i save the last found path and instead to try to reach the goal, try to reach the last found path? The player will have the option to build breakeable objects right into the path, then should pathfind work like this?: try to avoid then and find some other way, if none is found, then try to find a path passing thru those breakeables, if it's found then break then! that's all questions i tought up to now, i shall come up to more questions as i learn about Navigation Meshes :D

Quote: Autogenerating will not be a lot easy since all levels will be made using a grind layout.

What do you mean by 'grind layout'. Did you mean 'grid', perhaps?

I would run with a pathfinding grid rather than a navmesh. You don't need that much detail. As for the breakable items, those are just different movement costs to the edges. Very much like the differences that games put for road, plains, hills, forest, swamp, etc. It will try to take the easiest path, but opt for a slightly more difficult one if the total path cost is lower. That way, rather than only breaking through something if NO other path is found, it will do it when the cost of breaking through is less than the total normal path (whatever that cost may be).

thx for the replies.

@jyk:
oh, i meant grid layout ;D

@InnocuousFox:
yeah, now that you said, setting as a higher cost will a be better approach, however i intend to make my agents to have diferent sizes, and for then to colide with each other. so a player could put on a obstacle that will let the little ones pass, but not the big one, and this big one shall block the passage of the little ones too, untill the blockade is destroyed.. so i don't think that grid would work.. or would? i fear that if i set the grid too small the A* end up taking too much time, and i intend to make something like 500+ agents at the same time on some levels

For a normal simple tower defense game you will not have the need for such "Advanced" AI. You simply send a unit forward until it collides with something. At that point you can take for granted that there is some other direction that is possible to walk on, since you've run into an intersection. so first you check left, then right ( or the other way around ), and when you come across a way that is not blocked you just send the unit that way. This only works for the classic maze-like TD, but it's way simpler than to have an expensive A*-AI.

EDIT: Just read the last post. I guess you're stuck with A* anyways ^^
ignore me.

Use an adaptive quadtree to reduce the search space, that's usually how RTS do their pathfinding ( with various other techniques too, path caching, local heuristics, grouping etc.. )

It should be able to handle dynamic obstacles just fine. Here's a handy video :



Good Luck!

-ddn

can't watch youtube videos on my internship T.T

i program on my spare time here at work ;D

about the quadtree: would it be something like have some big areas that deem to be partialy passable and some that deem to be fully passsabe? where the partialy passable you can just pathfind inside it, and on the fully passable you can just get a straight line on it?

and i was thinking of using NavMeshs and it is seeming not as hard as i tought it would be to implement. My idea was to have the bigger as possible convex polygons for my NavMeshs, then when i pathfind i would just ask on which polygons i have to pass thru, and to decide a path inside then, it would be like: asking from which to which edges im going, then find the side of the edge that is closer to the destination (or the closer to the next Mesh edge i need to go), then from this point, find another on the edge that is "the agent colision radius" away from the found point, determine this new found point (somewhere in the middle of the desired edge) and put into a "desired points list". so that the agent will pass tru the NavMeshes always aiming for the further point in the list that is visible, doding dynamic obstacles that are on this or adjacent NavMeshes. Would it work proprialy or there is a better way to do it?

something like:
-- Agent Colision Radius.
* point in a Edge
*----------------* some edge
so:

*----------* is the edge i want to go
*----------* is the point closer to the next edge
*--------*--* is a new point at "agent colision radius" distance from previous point and this one will go to the "desired points to go" list

As i see using big NavMeshes it would reduce the amnmount of iterations on A* even for great distances. Most levels on my game will be Maze like.

I guess that right now, the only knologe i lack to implement this is Geeometry T.T

[Edited by - Guedez on May 29, 2009 2:23:01 PM]

That will work too, but splitting a nav mesh to take into account dynamic obstacles will be a pain ( since nav meshs are arbitrary geometry based off of the drawn 3D geometry or collision geometry ). I've seen hybrid schemes where people use a nav mesh in conjunction with a grid to handle dynamic obstacles, but I don't think your 3D world is complex enough to warrant that and that solution isn't perfect either.

In a tower defense game you will have lots of obstacles ( that's the core of the gameplay, as the players goal is to stop the horde ). Choose a data structure which allows you to dynamically add obstacles into the map. You can run a optimization pass on the quadtree generated grid and collate adjacent rectangles with shared edges of similar dimensions, further reducing the search space.

Good Luck!

-ddn

If the problem with the NavMeshes are because they might have some strange shapes when formed, this problem i have mostly solved with a simple modification on how a level will be formed.

you can play on either "compaingn or something" mode and "custom map" mode, and as well have a level editor tool inside the game. This level editor will use a grid and a heightmap to determine how the map will be. It will, based on the ground type and height of the zone create square nodes that fit with each other. something like this:

numbers means height.
* means unpassable, wall
# means river. W means waterfall


2 2 2 2 # # 2 2
2 2 2 2 # # 2 2
* * * * W W * * <- does not ocupy a node
1 1 1 1 # # 1 1
1 1 1 1 # # 1 1

each 4 numbers mean a square node, and each walkeable node have it's own NavMesh, what will try to merge with adjacent NavMeshes if possible. the NavGraph would be something like


p p p p r r p p
p p p p r r p p
c c c c u u c c <- this NavMesh is in the Y-X Axis and not Z-X Axis
p p p p r r p p
p p p p r r p p


where "p" stands for passable, "c" for climbable and "r" for river and "u" for unpassable.
a Agent could start building a ladder in case it seens more reasonable than climbing!


p p p p r r p p
p p p p r r p p
c c l l u u p p
p p p p r r p p
p p p p r r p p


something like this. so autogenerating and merging NavMeshes should be easy (if i knew how to do it on usual NavMeshes of course T.T)

in case of a dynamic obstacle, every unity will pathfind inside all NavMesh ignoring anything inside it, as it SHOULD be passable, in case it reports to have no Dynamic Obstacle on it. If it reports to have a Dynamic Obstacle, then the agent will pathfind from the entering edge of the NavMesh to the exiting edge of the NavMesh to see if it is or not passable at the time the path have been generated. As it enters the "I HAZ DYNAMIC OBSTACLE" NavMesh the agent will have to re-pathfind that especific Node, because all other nodes deem to still be passable.

something like this

During the BigPath pathfinding it will determine that point 1 is a good entry point, and point 2 is a good exit point. and it will save those two points.

. is free space.
# is blocked space.
| is a edge.
numbers are points.


|.....##..............|
|.....##..............|
|.....##..............|
|.....##..............|
1*....##..............|
|.********************2
|.....................|
|.....##..............|
|.....##..............|
|.....##..............|


But then when it finaly reaches point 1, the dynamic obstacle might have changed (it might not even be on the node anymore), so a path for 1->2 must be generated.


|.....##..............|
|.....##..............|
|.....................|
|.*******.............|
1*....##.*............|
|.....##..************2
|.....##..............|
|.....##..............|
|.....##..............|
|.....##..............|


Ok it will zig-zag after it dodges the dynamic obstacle, but still it quite works!(i hope)

My main idea on how use NavMeshes would be to save "I want to go" points on each conecting edge of the NavMeshes, then pathfind as it reach the point to the next point, what seens to be fast enough to be done everytime it enters a new NavMesh(would look stupidy, so it would need to change to "I want to go" edges!)

Sounds good, looking forward to seeing it in action :D

-ddn