| View previous topic :: View next topic |
| Author |
Message |
redhead Cheater
Reputation: 0
Joined: 21 Mar 2007 Posts: 47
|
Posted: Wed Oct 08, 2008 6:40 am Post subject: need help on algorithm (find the shortest path) |
|
|
Hi
I try to write a bot for a 2d game. (to run for me from point a to b)
Well, my bot already can move him and I can view the map.
(I mean, if there's a wall on location x,y or not)And my bot knows on wich location I am.)
An example of the map:
| Code: |
XXXX
XGEX
XXGGXX
XGGXGX
XXGKGGXX
XGGXXXGX
XGGSGGGX
XXXXXXXX
| (X = Wall, G = free place where I can walk, S = me
E= where I want to go)
location = x,y
S = 9,10
E = 10,5
The fastest path would be:
| Code: |
left(1)
up(3)
right(1)
up(1)
right(1)
up(1)
|
But how can I calculate this path automatically?
(I use C++ but I think this doesn't matter at all)
I'd be thanksfull for any kind of help
|
|
| Back to top |
|
 |
tombana Master Cheater
Reputation: 2
Joined: 14 Jun 2007 Posts: 456 Location: The Netherlands
|
Posted: Wed Oct 08, 2008 7:30 am Post subject: |
|
|
Try searching for the A-star pathfinding algorithm or A* if I remember correctly. It's a popular pathfinding algorithm.
What your bot needs to know for every block is to which other block it is connected, which is easy in your case: the ones next to it (up, down, left and right). It also needs to know the distance from a block to the destination (the distance when you draw a straight line, not nessecarily following the path. You can do this with pithagoras). This distance is just for speeding things up which is important when calculating a lot of paths in a very short time. Then the algorithm is able to calculate the shortest path.
You should be able to find c++ source codes for it on the net.
|
|
| Back to top |
|
 |
redhead Cheater
Reputation: 0
Joined: 21 Mar 2007 Posts: 47
|
Posted: Thu Oct 09, 2008 6:25 am Post subject: |
|
|
Thanks, I got it working with the A* method .
|
|
| Back to top |
|
 |
|