Pathfinding with waypoints, instead of grid.
Blitz3D Forums/Blitz3D Programming/Pathfinding with waypoints, instead of grid.
| ||
| Anyone have any ideas how this is done? do you overlay a grid on top of the waypoints, and work like you do from A* pathfinding? Currently, finding the shortest paths is a matter of looping through every possible path. Which isn't ideal... |
| ||
| For instance, here's a diagram i've knocked together, for referencing, so i can visualise what you mean when you explain. Would appreciate any help i could get on this! And i have read articles on this too from google. Just finding it hard to grasp.  So, say i wanted to go from 1 to 13, what would be the rough steps i'd take? |
| ||
| I know one, created by Andrew Pye... I've sent an email with the file to you, with the .rar extension. |
| ||
| Can someone send me it too.. (address in profile) |
| ||
| Is Done! =D |
| ||
| Thanks man! i'll have a good read over it :o) I'll forward the email to you boomboom. |
| ||
| Got it, thanks :) |
| ||
| Hmmm, very interesting code man, but i'm looking for more of a straighforward explaination as to how waypoints are traversed to obtain forinstance the shortest route. Anyone shed some light? :D Looks great code btw EmerGki |
| ||
| Ross: I think the algorithm you're looking for is called Dijkstra's I'll see what I have on that when I get home tonight. |
| ||
| Thanks man. I'm just really struggling to get my head round it. Once it clicks I'll be fine! Took me ages to get types, then once it clicked, i wondered how i did without them and they were really easy. Same thing here i guess :o) It's really hard to make certain games without using pathfinding, and it's really holding me back. |
| ||
| Does this help? http://ai-depot.com/Tutorial/PathFinding.html |
| ||
| Hi Ross, What you have there is a weighted graph, which is ideal for pathfinding using A* or whatever else you might want. You might also want a directed weighted graph ( I think my terminology is correct here ) in which connections between nodes are not assumed to work both ways. If your maps need this, then you implement this by having connections only work one way, so you have two connections if you can go both ways. This gives you the bonus that going from a to b can have a different cost than going from b to a. ( For example if b is much higher than a, it would make sense that going from a to b cost more than going from b to a because it's uphill. ) What you want is to keep a list ( array for speed ) of connections ( lines in your diagram above would be connections ) available from each node. Each connection has a "cost" value which is the cost of going along that connection, and of course the node which the connection comes from, and the node it goes to. Nodes may be stored as B3D objects or just an integer index if you prefer. That should be all the information you need from your weighted graph to be able to plug in A* pathfinding. There's really no reason for A* to be any better suited to a grid than any other graph. It just wants a list of possible connections and the cost of each connection, along with which nodes are connected. Ian Millington's book "Artificial Intelligence For Games" has several chapters on weighted graphs, pathfinding algorithms and much more, and I've found it very useful. |
| ||
| Ok guys thanks. Some helpful things to read there. Thanks for the info Gab, mucho appreciatanty :o) |
| ||
| Whoa, that's a pricey book :-O Is it worth the money Gab? |
| ||
| If I may add my .02, Is is a very good book. I got a lot out of it. The Mat Buckland book is also very good and, I believe, covers, pathfinding. |
| ||
| Hmm, thanks man. I've accidently double posted a request for recommendations :oS But thanks, i might give it a shot. Need to do it when the missus leaves, or i'll get shot... |
| ||
| Hmmm, thanks for that link Morbius. That is pretty simple to understand :o) May get long winded when a complex network of nodes is used, but it's still great stuff! Thanks :D |
   |