Author Topic: Path Finder algorithm  (Read 3957 times)

Offline ale

  • byte
  • *
  • Posts: 1
    • View Profile
Path Finder algorithm
« 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

Offline rolz

  • float
  • ****
  • Posts: 280
  • Technocrat
    • View Profile
Path Finder algorithm
« Reply #1 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

Regards,
Andrei

Offline EgonOlsen

  • Administrator
  • quad
  • *****
  • Posts: 12295
    • View Profile
    • http://www.jpct.net
Re: Path Finder algorithm
« Reply #2 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.