| View previous topic :: View next topic |
| Author |
Message |
Cheat Engine User
Something epic
![]() Reputation: 60
Joined: 22 Jun 2007
Posts: 2071
|
 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: 1857
|
| 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: 1887
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 |
|
|
Cheat Engine User
Something epic
![]() Reputation: 60
Joined: 22 Jun 2007
Posts: 2071
|
| 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 |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
