Cheat Engine Forum Index Cheat Engine
The Official Site of Cheat Engine
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 


need help on algorithm (find the shortest path)

 
Post new topic   Reply to topic    Cheat Engine Forum Index -> General programming
View previous topic :: View next topic  
Author Message
redhead
Cheater
Reputation: 0

Joined: 21 Mar 2007
Posts: 47

PostPosted: Wed Oct 08, 2008 6:40 am    Post subject: need help on algorithm (find the shortest path) Reply with quote

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 Smile
Back to top
View user's profile Send private message
tombana
Master Cheater
Reputation: 2

Joined: 14 Jun 2007
Posts: 456
Location: The Netherlands

PostPosted: Wed Oct 08, 2008 7:30 am    Post subject: Reply with quote

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
View user's profile Send private message
redhead
Cheater
Reputation: 0

Joined: 21 Mar 2007
Posts: 47

PostPosted: Thu Oct 09, 2008 6:25 am    Post subject: Reply with quote

Thanks, I got it working with the A* method Smile.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Cheat Engine Forum Index -> General programming All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2005 phpBB Group

CE Wiki   IRC (#CEF)   Twitter
Third party websites