Hi! I am working on a 3D game using Delphi. Right now I am searching for a Pathfinding. The samples I found have one big disadvantage for 3D, they have every single step as a waypoint so only use 45° steps. I don't wanna use 45° only, if possible. I don't want all points like this: I only want the points I need so I can set my angle to next point until I am there: Is this possible somehow? Or is there an Other Sample / Algo to do so? Thanks, Firle

There are two possibilities for you.

First one (and easiest), keep your current representation (squares) but smooth the path after you have found it.

Second one, use a different representation for your pathfinding nodes, like points of visibility, or navmeshes. But you will probably still have to smooth your path.

Here is a dumb and easy way of smoothing your path.

do
For every node in your path, except the first and last
If you can draw a straight line from the previous to the next node
remove that node
until you cannot remove any more nodes

Have fun !

You could simply post process your path and remove all the unnecessary nodes.

One way to do it would be to :

Check that you have at least 3 nodes
Set the start node as start, 3rd node as target
do
if a line (one unit wide) can reach the target node from the start node
pop "target -1" node (in the first loop, that would be the 2nd node
advance target to the next node
else
move start to the current target position, and advance target 2 nodes
while target < end node

Not sure if it all makes sense... first thing I wrote after waking up, but that should do the job for most cases.

You could also switch to a polygonal representation of your nav mes instead of using grids, but that would be a lot more work.

Cheers

Eric

Hello,

Thanks for your ideas.

I guess to remove nodes I don't need is the necessary way.

I am using a 2 dim array.

I will try to find a A* pathfinding sample for Delphi and enhance it.

firle

Quote: Original post by firlefanz
Hello,

Thanks for your ideas.

I guess to remove nodes I don't need is the necessary way.

I am using a 2 dim array.

I will try to find a A* pathfinding sample for Delphi and enhance it.

firle

A* / Dijkstra is a graph algorithm that *anyone* in computer science should coded at least once in its life. Why not start now :)

I am working on this same sort of thing.

If my units are free moving and not stuck to a grid, how do I apply A*?

How do I break my map into grids? My units aren't stuck to walking through a grid. They can walk a straight line from point A to point B.

If I do deivide my map into grids to find the best path, do I choose grid units the same width of my unit? So, if a grid unit is occupied, I know my unit won't fit?

But what if a grid psace is occupied, but at the very southern edge. And the grid unit above is occupide at the very top edge, then it is possible to pass between the units occupying the two grid spaces. But I eliminate that as a choice?

This is new to me, as I have never done any real AI type of stuff.

Right now, I have units that just walk straight from A to B. If they encounter another unit, and it is moving they wait for it to move out of the way, if it isn't moving, they go around it. I have no structures on the battlefield to avoid yet.

Quote: Original post by TaskyZZ
I am working on this same sort of thing.

If my units are free moving and not stuck to a grid, how do I apply A*?

How do I break my map into grids? My units aren't stuck to walking through a grid. They can walk a straight line from point A to point B.

If I do deivide my map into grids to find the best path, do I choose grid units the same width of my unit? So, if a grid unit is occupied, I know my unit won't fit?

But what if a grid psace is occupied, but at the very southern edge. And the grid unit above is occupide at the very top edge, then it is possible to pass between the units occupying the two grid spaces. But I eliminate that as a choice?

This is new to me, as I have never done any real AI type of stuff.

Right now, I have units that just walk straight from A to B. If they encounter another unit, and it is moving they wait for it to move out of the way, if it isn't moving, they go around it. I have no structures on the battlefield to avoid yet.

Dividing into a grid is a waste of cpu and memory, meshes are much more efficient. Anyway, A* will give you ONE path, then its up to you to navigate this path like there was no grid/mesh. Or you can go with dynamic A*, creating the navigation mesh as you go.

Can you explain this idea of navmesh? I am not getting it, sorry. :)

Lets say I have a large space and some trees and buildings. How do I build a navmesh without using some sort of grid? Is this something that has to be built ahead of time?

Edit: I guess I should point out that I am doing it in 2D, for an RTS style game. Does that affect whether navmesh is better than A*?


[Edited by - TaskyZZ on October 9, 2006 6:56:32 PM]

A navmesh replaces a grid. Instead of having a grid of squares, you have a "mesh" or arbitrary convex polygons. Search around, there is an excellent pathfinding demo that shows the difference between all sorts of representation.

Your mesh should be computed when you save your map, from the vertices of obstacles. There is an article about building navmeshes in the book AI Wisdom (the first one). But maybe you should stick to grids, and just smooth your path over. Just divided your 2d space into small squares roughly bigger than a unit. No magic solutions! Check out articles that specifically target RTS pathfinding.

Thanks for the help. Will look at getting my hands on that book as well.