www.jpct.net

jPCT - a 3d engine for Java => Support => Topic started by: ale on November 23, 2005, 09:25:23 am

Title: Path Finder algorithm
Post by: ale on November 23, 2005, 09:25:23 am

He All!
I have a 3ds model similar to fps demo and
I want to implement a Path Finder algorithm like A* (view the book Development Game in Java).
I must to use Portals? If yes, it's possible to generate Portals in automatic manner in load model procedure? Exist same examples in jpt engine?
Tanks

Title: Path Finder algorithm
Post by: rolz on November 23, 2005, 09:38:32 am

you could use steering algorhitms but it would be simplier if you apply A* -
Split area around your character to squares and apply A* to the resulting grid. You may increase/decrease cell size to adjust accuracy/performance

EDIT: this is how it looks like in Technopolies:
"unpassable" squares are marked with red ellipses

(http://home.ripway.com/2005-5/312079/shot101-pathfinding.jpg)

Title: Re: Path Finder algorithm
Post by: EgonOlsen on November 23, 2005, 05:19:28 pm

Quote from: "ale"

I must to use Portals? If yes, it's possible to generate Portals in automatic manner in load model procedure?

Portals in jPCT are for geometry culling only. They won't help you in your case, there is no way to auto-generate them (because it's almost impossible to place them as good as an artist would be able to do it) and i don't recommend to use them. The code base they rely on hasn't been tested by anyone for ages now. Use octrees instead.
However, for A* use the grid approach that rolz mentioned. Paradroidz (albeit not using A*) is doing the same thing. It works grid based only (for AI, collision detection, movement) for entities that are invisible and uses a combination of grid/geometry based for entities that are. Works just fine.

Edit: Inspired by this thread, i've changed Paradroidz' path finding to a slightly modified A*...works better than before now.