patchfinding

patchfinding

Post by MX^Addic » Fri, 11 Jul 2003 20:22:15



Hi

I'm looking for some tuts about patchfinding in fully 3d environments.
Any links, comments, sugestions witch algos are suitable ??

THX

 
 
 

patchfinding

Post by Mickael Pointie » Fri, 11 Jul 2003 20:47:18



> Hi

> I'm looking for some tuts about patchfinding in fully 3d environments.
> Any links, comments, sugestions witch algos are suitable ??

Well, for "Patch" finding, you better have a good memory tracker, some
lint program, and a good debogger ;)

For "Path" finding, that's a total different beast =)

Try looking for "A*" (A star) using google, from there you will find a
lot of articles about how to perform a good 3D path finding.

    Micka?l Pointier

 
 
 

patchfinding

Post by MX^Addic » Fri, 11 Jul 2003 21:06:41





> > Hi

> > I'm looking for some tuts about patchfinding in fully 3d environments.
> > Any links, comments, sugestions witch algos are suitable ??

> Well, for "Patch" finding, you better have a good memory tracker, some
> lint program, and a good debogger ;)

sorry, my english sucks :(

Quote:

> For "Path" finding, that's a total different beast =)

> Try looking for "A*" (A star) using google, from there you will find a
> lot of articles about how to perform a good 3D path finding.

thx, and yet another question ... is there any pathfinding algo that may
utilize portals information from level (3d)  ?
 
 
 

patchfinding

Post by Mikko 'memon' Monone » Fri, 11 Jul 2003 21:41:47



> thx, and yet another question ... is there any pathfinding algo that may
> utilize portals information from level (3d)  ?

You should be able to use that information with A*. The basic idea of A*
is to find the shortest path (for example, or the most economical...) from
point A to point B in a graph. The graph can be for example a grid, like a
chess board, or it can be arbitrary net of nodes connected to eact other.

One good place worth checking out is the AI depot at:

        http://ai-depot.com/Main.html

--memon


                            uow3W                 uow3w~/6Jo'3p15u1'mmm

 
 
 

patchfinding

Post by Mickael Pointie » Fri, 11 Jul 2003 21:51:58






>>> Hi

>>> I'm looking for some tuts about patchfinding in fully 3d
>>> environments. Any links, comments, sugestions witch algos are
>>> suitable ??

>> Well, for "Patch" finding, you better have a good memory tracker,
>> some lint program, and a good debogger ;)

> sorry, my english sucks :(

Mine also.
But well, I corrected you mostly because you better have to use the
right word when you use search engines =)

Quote:>> For "Path" finding, that's a total different beast =)

>> Try looking for "A*" (A star) using google, from there you will find
>> a lot of articles about how to perform a good 3D path finding.

> thx, and yet another question ... is there any pathfinding algo that
> may utilize portals information from level (3d)  ?

Most algorithm simply try to find the "less expensive" path between
interconnected nodes. To find that they compute the cost to move from a
node to another. So you can simply consider that two portals/teleporters
are two nodes with a small or null cost.
With this kind of system you can compute the cost to move from a node to
another taking into consideration things like the lenght, but also the
steepiness (so you can have to deal with different costs for going from
A to B than from B to A), the difficulty (it's harder to move in water
or sand than on tarmac), the dangerosity (will help a character choose
the less dangerous path), and so on... dealing with portals is only a
small implementation detail.

The hard part in pathfinding is not the pathfinding, it's the way you
put nodes on the map, because most automatic algorithm are quite bad at
doing that, specialy if you add to the equation the fact you could jump
over clifs instead of following it, and things like this... or "why
following the road if you have a jet pack ?"...

    Mickael Pointier

 
 
 

patchfinding

Post by Lewis Seller » Sat, 12 Jul 2003 05:26:18


Quote:>> I'm looking for some tuts about patchfinding in fully 3d environments.
>> Any links, comments, sugestions witch algos are suitable ??

See http://www.intrafoundation.com/pathfinder.asp for PathFinder2D.
Open-source C++. Now, it is only 2D true, but it has 5 different
variations of A* to fool around with which can be useful if you have
no experience at all with A* (you didn't say).

I am working one something similiar that tests pathfiding in a 3d
environment that should be up soon. The A* itself isn't all that
different in 3D, but you do generally need to quanitfy the 3D space
into a series of nodes (or portals, or what-have-you) usually through
another series of raycasting or bounding-boxes.

Essentially it's a two-step process, with the node quantification
taking place on your dev machine or when the map loads the first time.

--min