View previous topic :: View next topic 
Author 
Message 
Holland Something epic Reputation: 60
Joined: 22 Jun 2007 Posts: 2076

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


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 


Slugsnack Grandmaster Cheater Supreme Reputation: 71
Joined: 24 Jan 2007 Posts: 1858

Posted: Mon Apr 26, 2010 3:08 am Post subject: 


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 


Flyte Peanuts!!!! Reputation: 6
Joined: 19 Apr 2006 Posts: 1888 Location: Canada

Posted: Mon Apr 26, 2010 3:13 am Post subject: 


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 


Holland Something epic Reputation: 60
Joined: 22 Jun 2007 Posts: 2076

Posted: Mon Apr 26, 2010 5:20 am Post subject: 


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 


Uzeil Moderator Reputation: 6
Joined: 21 Oct 2006 Posts: 2411

Posted: Wed Jun 09, 2010 4:50 am Post subject: 


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.
_________________


Back to top 


