Hi,

I currently have a tile-based landscape engine but i want to change it into a much more extendable engine. I wan't to use collision detection with the underground. An avatar is not restricted to tiles anymore and I can use a drawbridge for example. The problem is that I don't have a clue how to do a route-find algorithm (I'm currently using A* but that's restricted to tile-based landscapes). I'm currently using multiple floors and such a strict floor devision have to be removed because the floor model has to be more dynamic (for like I said for example a drawbridge). Does someone knows how to do both collision detection with the underground and the route-find algorithm? I don't want to use Newton or other external libary's.

You can use A*. A* is not restricted to tiles. You also can use it with graphs (or mesh. Don't know how it's called. ). So you just have to define a "graph-structure" for your Tiles.
For example: If you have allways the same tiles, you can make the nodes of the graph be part of your tiles. If you want to use unusual tiles, you can build an editor where you can place the nodes manually. So your route finding algorithm will allways have a proper base.

(I thougt the Unreal maps had such a structure, for the bots to find there route, through the levels, too.)

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Unreal Tournament "1" had an option in the editor, which generated pathnodes automatically. But this was very buggy and the designers removed this option in UT 2004. It was always the best solution to place the nodes manually.

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

If your Units can only move like this:



it should not be a problem to create include a pathfinding system. You only have to check if the next highlevel is to high or not.
That's all.

But if you more I am interesset in such a 360 degree pathfing procedure,too. (because it is very difficult to realise that)


Flo

_________________
Danke an alle, die mir (und anderen) geholfen haben.
So weit... ...so gut

Navigation meshes are a good option for pathfinding and collision detection in arbitrary environments. You build a graph of walkable triangles and connect them by their edges. I guess it's best if you perform a google - search about them.

But they have a few disadvantages which can be very hard to overcome:
- they are quite static so you will have to do seperate walkability and collision tests for your dynamic objects.
- if your avatars differ in size you will have to make a compromise between some creatures walking into walls or some creates not able to walk close enough to the wall to reach certain things. Or you need a navigation mesh for each creature.
- in my opinion they are a waste of time for large outdoor environments with a few trees or buildings on them. In this case an octree might do a better job. But still they are useable in such environments.
- they might be a problem if you implement game logic like jumping (maybe jumping over a river), opening or closing a door and such.

I once tried A* on a very big map (for that rivercreation algo on Gamedev) and it took very long (a few sceonds).
But I guess you can speed it up by increasing the stepsize of your pathfinding algo when going further away from the startpoint. In addition you could add an lowres waynet with a precomputed set of shortest pathes. Then A* can do the first few nodes and then you switch to the precomputed set.

_________________
[18:30] tomok: so wie ich das sehe : alles. was nich was anderes ist als nen Essay ist nen Essay

hi, i'm a signature viruz, plz set me as your signature and help me spread

Thanks for all your reactions. I'm going to use A* in combination of with a "collision tree" containing planes. It will be a more dynamic solution that makes elevators possible for example.

@AL: A* isn't slow unless there is no solution. You can solve this problem by adding a maximal amount of steps.

Depends on your graph. If you send it through 1 000 000 nodes with a bad heuristic...

_________________
[18:30] tomok: so wie ich das sehe : alles. was nich was anderes ist als nen Essay ist nen Essay

hi, i'm a signature viruz, plz set me as your signature and help me spread