Sign in to follow this  
firlefanz

Pathfinding for Delphi in 3D

Recommended Posts

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: [img]http://www.ericbehme.de/bilder/temp/Path1.JPG[/img] I only want the points I need so I can set my angle to next point until I am there: [img]http://www.ericbehme.de/bilder/temp/Path2.JPG[/img] Is this possible somehow? Or is there an Other Sample / Algo to do so? Thanks, Firle

Share this post


Link to post
Share on other sites
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 !

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
TaskyZZ, check out the little app at this link(click the picture)
clicky

It demonstrates a bunch of methods of pathfinding.

The shortcutting smoothing several people have mentioned works great in 2d games, but typically has issues in 3d games, for similar reason to why points of visibility has issues in 3d games. Simply having line of sight between 2 nodes doesn't mean you can skip all the nodes in between in 3d. If your A* is set up properly you will get an optimal path. There are reasons the path planning usually makes non straight paths, that's to avoid holes, pillars, etc. If you start shooting rays and shortcutting the path you are going to run into more problems than you solve most likely, mostly with holes that the shortcuts could run the guys into. Just consider if that is an issue with the game you are working on before you implement it.

Much of the time the smoothness of the path doesn't matter so much as the way you make your agent follow it. If you lock him to the line then it will look bad, if you have him seek to a point always ahead of him on the path, he will naturally curve into the corners, though you need to make sure he doesn't cut corners too much so as to run into stuff he shouldn't. A common method is having the agent seek to each point in the path, and it considers it reached when he gets within some distance of the point, which he will then go to the next point. This has similar effect of rounding out corners of otherwise angular paths. It's not perfect, but it's very simple and produces reasonable results. Your search space representation has alot to do with your path post processing options.

[Edited by - DrEvil on October 11, 2006 11:54:16 AM]

Share this post


Link to post
Share on other sites
Thanks.

I am still learning this stuff and appreciate all the help. You make some good points to think about, some of which I had been considering.

I don't get a lot of time to code, so I haven't been able to play with this in the last few days, but I will be jumping on it again this weekend for sure. It is fun makeing changes to the AI and then seeing the little guys walking around putting it to use. Seeing how they break my vision of it and then making changes to push them back along the path of my vision. :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this