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 


I need to know how to find the shortest path.

 
Post new topic   Reply to topic    Cheat Engine Forum Index -> Game Development
View previous topic :: View next topic  
Author Message
Holland
Something epic
Ban
Reputation: 60

Joined: 22 Jun 2007
Posts: 2078

PostPosted: Mon Apr 26, 2010 2:48 am    Post subject: I need to know how to find the shortest path. Reply with quote

I am currently making a project for my new school but I've got to find a way to find the shortest path to a certain point. Well, it doesn't necessarily have to be the shortest path, just a path that works. It's tilebased, so that's not a problem. How would I do this or where can I find sources (as in information)on this?
Back to top
View user's profile Send private message
Slugsnack
Grandmaster Cheater Supreme
Reputation: 71

Joined: 24 Jan 2007
Posts: 1858

PostPosted: Mon Apr 26, 2010 3:08 am    Post subject: Reply with quote

tile based ? or grid based ? if it's just a grid, you can just go diagonal till you meet the 'y' coord then go right/left from there. else you can model it as a graph then use shortest path graph theory.

can you give some more info ?
Back to top
View user's profile Send private message
Flyte
Peanuts!!!!
Reputation: 6

Joined: 19 Apr 2006
Posts: 1888
Location: Canada

PostPosted: Mon Apr 26, 2010 3:13 am    Post subject: Reply with quote

Go through the list here and find one that suits your project.

A* is the most popular one, but since I don't know what you want to do it with it, it may not be the best for your purposes.
Back to top
View user's profile Send private message
Holland
Something epic
Ban
Reputation: 60

Joined: 22 Jun 2007
Posts: 2078

PostPosted: Mon Apr 26, 2010 5:20 am    Post subject: Reply with quote

Slugsnack wrote:
tile based ? or grid based ? if it's just a grid, you can just go diagonal till you meet the 'y' coord then go right/left from there. else you can model it as a graph then use shortest path graph theory.

can you give some more info ?
Tile based could be seen as grid based you know. But Flyte pretty much gave me what I needed, so I am good and this can be closed.
Back to top
View user's profile Send private message
Uzeil
Moderator
Reputation: 6

Joined: 21 Oct 2006
Posts: 2411

PostPosted: Wed Jun 09, 2010 4:50 am    Post subject: Reply with quote

I'm really bad about looking up algorithms when asked to make one.

So when asked to make a pathfinder(maze solver in this case), I made the following.

Code:
//function is first called with the coordinates of the Start location.
function SolveMaze(maze: array of String; X, Y: Integer): Boolean;
begin
  Result := True;
  //if I'm about to try to move to the edge of the maze, if it's a wall('#') or if I've already been there, return False
  if (Y > length(maze)) or (X > length(maze[Y])) or (X = -1) or (Y = -1) or
    (maze[Y][X] = '#') or (maze[Y][X] = '.') then
  begin
    Result := False;
  end
  else if maze[Y][X] = 'E' then //destination point
  begin
    Result := True;
  end
  else
  begin
    //put a dot to show I've been there
    maze[Y][X] := '.';
    drawMaze(maze); //print current progress
    //recursively call function for all possible movements.
    if (not SolveMaze(maze, X + 1, Y)) and (not SolveMaze(maze, X - 1, Y)) and
      (not SolveMaze(maze, X, Y + 1)) and (not SolveMaze(maze, X, Y - 1)) then
    begin
      //put a space(erases my position before tracing back in the call stack if I reached a dead end, which erases my steps taken.
      maze[Y][X] := ' ';
      Result := False;
      drawMaze(maze); //print current progress
    end;
  end;
end;


Note: I know you can rewrite the 'not, and not, and not, and not' to be a 'not (or or or)', and can change the 'end else if' 's to utilize Exit, but I don't feel like editing now that I already closed the IDE. Not that pretentious.

_________________


Mini Engine v3.0
Mipla v1.0

Reposted old threads out of the MS section.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Cheat Engine Forum Index -> Game Development 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