Exploring a map - dijkstra?
hi, im a newbie in game programming (just taking it at uni this year) so please bear with me...
im working on a game where the player initially has no idea about the map. so the player has to explore the map and find stuff (Player has limited vision). There are several types of obstacles that he has to get past. Is there a specific kind of algorithm that is suited to 'exploring'? Im currently thinking of dijkstra, but im not sure...Pls advice!
Thnx!!
# 1
You could draw the map, then draw a Black-Region on top of it. As you explore an area, that region would disappear in the areas you explored. Does that make sense?
# 2
The A* search algorithm is a classic path finding algorithm where there is limited knowledge concerning the total map: http://en.wikipedia.org/wiki/A*_search_algorithm
# 3
yes but what i want to know is HOW to make the AI player walk about.. currently my AI player keeps running into dead ends and keeps going in circles.! I need to get back to the starting block in a certain time limit too, for that return path, im using A*.
Is dijkstra an effective algo for what i wnt to do?i cant figure out how to use A* for exploring since i hav no prior knowledge abt the map and hence what do i use for heuristics?
Please help!!!
# 4
> yes but what i want to know is HOW to make the AI
> player walk about.. currently my AI player keeps
> running into dead ends and keeps going in circles.! I
> need to get back to the starting block in a certain
> time limit too, for that return path, im using A*.
Then you think you are using the A* algorithm. Because if your player keeps going in circles, you're not using A*.
> Is dijkstra an effective algo for what i wnt to do?i
> cant figure out how to use A* for exploring since i
> hav no prior knowledge abt the map
A* is just a variation on Dijkstra's algorithm. Both can be used if no prior knowledge about the map is known.
> and hence what do i use for heuristics?
That's for you to decide. If your map used (x,y) coordinates, then you could use the length of a straight line from your current position to the goal as your estimate.
> Please help!!!
Please stop posting such cries at the end of your message. You're getting response, don't you?
# 5
Perhaps this thread can be of use to you: http://forum.java.sun.com/thread.jspa?threadID=5130284&tstart=0I gave an example of an A* algorithm in reply 3.
# 6
A* only works for known territory, so get your player to explore using a method like 'floodfill', 'keep turning left', 'take random direction', whatever.Make your player remember the terrain in an internal map and then use A* to get to important places when required...
# 7
> A* only works for known territory,
> ...
No.
With the A* algorithm, the player (or robot) knows the starting, and end point. The algorithm adjusts the path while exploring the map and always finds a "best path". Usually, a part of the map will be even left unexplored.
Perhaps you want to read up on the algorithm:
http://en.wikipedia.org/wiki/A*_search_algorithm
# 8
>The algorithm adjusts the path while exploring the map
Hate to be picky prometheuzz, but A* works on a graph of nodes - unless you know where the nodes are and the distances between them then you can't use the algorithm... If you only have two nodes in your graph (start and finish) then all A* can do is find one solution: a straight line between them!
Perhaps you could quote from the wiki page the bit where it says 'builds the graph as it goes' - you have read it haven't you? ;o)
# 9
thanks for all the replies guys.
Actually im already using A* for the return path (which seems to work because it always finds itself to the starting point)
My problem is the 'exploration' algo. Because there isnt a particular target so I dont need a 'shortest path'. the robot has to explore the map as much as he can, and he doesnt know abt the map either.
im thinking of trying BFS as well. Is that a good idea?
# 10
> Hate to be picky prometheuzz, but A* works on a graph
> of nodes -
Yes, and a map can be expressed as a graph of course (a map is just a set of Cartesian points connected to each other).
> unless you know where the nodes are and
> the distances between them then you can't use the
> algorithm...
You discover it while you are walking through your map/graph.
> If you only have two nodes in your graph
> (start and finish) then all A* can do is find one
> solution: a straight line between them!
That is obvious. Your point being?
> Perhaps you could quote from the wiki page the bit
> where it says 'builds the graph as it goes' -
You probably misunderstood. Given a start- and end point and a (unexplored) graph/map, the A* algorithm can be used to find an optimal path between them.
> you have read it haven't you? ;o)
Yes, I have.
And I have implemented it.
And it works as I described.
# 11
> thanks for all the replies guys.
> Actually im already using A* for the return path
> (which seems to work because it always finds itself
> to the starting point)
> My problem is the 'exploration' algo. Because
> there isnt a particular target so I dont need a
> 'shortest path'. the robot has to explore the map as
> much as he can, and he doesnt know abt the map either.
> im thinking of trying BFS as well. Is that a good idea?
I'm pretty sure Simon__1st can assist you from here on.
; )
Good luck.
# 12
BFS is a simpler version of A* which again only works with known areas...
Consider your problem; you have a robot in an unknown environment and it's task is to explore, then get back to 'home' within a certain time.
A* is perfect for getting home, what you need is an efficient way of exploring as much territory as possible as fast as possible before that time elapses...
The best exploration method I ever found was the 'keep left/right' method; robot goes forward until it hits an obstacle where it then turns left (if it hasn't been there already), then robot goes forward again until it hits an obstacle where it then turns right (if that's unexplored), and so on.
You keep going ways you haven't been yet... Keep a record of 'unexplored' areas and use A* to return to one of them if you hit a dead end...
Eventually this method will explore the whole environment, but in the short term it'll find as much as it can. Depends what your robot looking for.
Think of yourself in an unknown, pitch-black environment looking for either a lightswitch or a flashlight on the floor somewhere - what would you do?
# 13
thanks Simon. Will try out ur idea! I did use a sort of left/right method, but my error was to [keep using/i] it even when i hit a dead end. Didnt occur to me that i could use A* to exit from a dead end to an unexplored area as well..thanks again!
# 14
> BFS is a simpler version of A* which again only works
> with known areas...
I find your terminology still vague. What do you exactly mean by "known areas"?
I wouldn't call a BFS a simplified version of A*. Dijkstra's algorith is a simplified version of A*. A BFS is just a brute force way to explore your entire graph/map.
If the robot knows a starting- and end-coordinate, it does know something about the map. And by moving from one coordinate to the other, it can estimate a minimum number of steps towards the finish, which A* does.
> Consider your problem; you have a robot in an unknown
> environment and it's task is to explore, then get
> back to 'home' within a certain time.
> A* is perfect for getting home, what you need is an
> efficient way of exploring as much territory as
> possible as fast as possible before that time
> elapses...
A* can be used to get there. When the robot/player gets there, it just goes back the same way as it came, since A* finds the best (optimal) path between 2 nodes (coordinates).
> The best exploration method I ever found was the
> 'keep left/right' method; robot goes forward until it
> hits an obstacle where it then turns left (if it
> hasn't been there already), then robot goes forward
> again until it hits an obstacle where it then turns
> right (if that's unexplored), and so on.
What do you mean by "best exploration method"? Best in what way?
Take this maze for example:
s = start
f = finish
x = wall
xxxxxxx
x s f x
x xxx x
xx
xxxxxxx
Suppose the robot is programmed to always go left if it hits a wall (and turns around when hitting a dead end), then it will take him 10 steps to reach the finish. An A* algorithm will first estimate the cost by going left or right (in the above example). Since the coordinate to the right of the start-coordinate is closer to the finish, it will decide to go right instead of going left, thus reaching the finish in two steps.
# 15
What's all this talk about BFS? If I understand the situation correctly (AI explores, moving at a fixed speed, discovering the edges from a node when it reaches that node) then DFS makes a lot more sense. BFS would mean an awful lot of doubling back, and thus take longer to explore the whole map.
# 16
> I wouldn't call a BFS a simplified version of A*.
> Dijkstra's algorith is a simplified version of A*. A
> BFS is just a brute force way to explore your entire
> graph/map.
True, i agree.
> If the robot knows a starting- and end-coordinate, it
> does know something about the map.
Unfortunately, in my case the robot only has a starting point. It does NOT have a specific goal, thereby no end co-ordinate. The whole point of the game is to explore the map.
> Suppose the robot is programmed to always go left if
> it hits a wall (and turns around when hitting a dead
> end), then it will take him 10 steps to reach the
> finish. An A* algorithm will first estimate the cost
> by going left or right (in the above example). Since
> the coordinate to the right of the start-coordinate
> is closer to the finish, it will decide to go
> right instead of going left, thus reaching the finish
> in two steps.
Yes if the robot knows the map. This method can be used for going home, and also to backtrack when robot goes down to a deadend. But A* alone cannot be used for the whole purpose of exploring.
The key issue i have is NOT finding a shortest path. It is exploring - the more, the better.
# 17
> ...
> Unfortunately, in my case the robot only has a
> starting point. It does NOT have a specific goal,
> thereby no end co-ordinate. The whole point of the
> game is to explore the map.
Then A* and Dijkstra are no options.
> ... This method can be used for going home ...
If you have explored (a part of) your map and found your end-point and want to return to your starting point, you don't need an A* or Dijkstra-algorithm because you have done the exploring already.
If you create some sort of a recursive BFS algorithm beginning from your starting point, from every unexplored coordinate you explore further providing a path of coordinates you have visited as a parameter in every recursive call. When you hit the finisch coordinate, you have the shortest path back to your starting point already.
# 18
> ...
> If you have explored (a part of) your map and found
> your end-point and want to return to your starting
> point, you don't need an A* or Dijkstra-algorithm
> because you have done the exploring already.
> If you create some sort of a recursive BFS algorithm
> beginning from your starting point, from every
> unexplored coordinate you explore further providing a
> path of coordinates you have visited as a parameter
> in every recursive call. When you hit the finisch
> coordinate, you have the shortest path back to your
> starting point already.
This is what I mean:import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class MazeExplorer {
Maze maze;
Path foundPath;
public MazeExplorer(Maze maze) {
this.maze = maze;
this.foundPath = null;
}
public void solve(Tile current, Path path, Set<Tile> visited) {
if(foundPath != null) { return; } // we found a path: quit
path.add(current);
visited.add(current);
if(current.type == Type.FINISH) {
foundPath = path;
} else {
List<Tile> neighbours = maze.getNeighbours(current);
for(Tile temp : neighbours) {
if(!visited.contains(temp)) {
Path copy = new Path(path.tiles);
solve(temp, copy, visited);
}
}
}
}
public static void main(String[] args) {
// the outer tiles need to be walls
// x = wall, S = start, F = finish
String[] data = {
"xxxxxxx",
"xSx Fx",
"x x x x",
"xx x",
"xxx x x",
"xx",
"xxxxxxx"
};
Maze maze = new Maze(data);
MazeExplorer explorer = new MazeExplorer(maze);
System.out.println(maze);
explorer.solve(maze.start, new Path(), new HashSet<Tile>());
// Note that the upper left corner = (0,0)
System.out.println(explorer.foundPath);
}
}
Which produces the following output:xxxxxxx
xSx Fx
x x x x
xx x
xxx x x
xx
xxxxxxx
Path:
[(1,1), (1,2), (1,3), (2,3), (3,3), (3,2), (3,1), (4,1), (5,1)]
As you can see if you look at the solve(...) algorithm, I only do a BFS to explore the map. When I stumble upon the (unknown) finish, I know the shortest path to it already: no need to find a path back to the starting point.
These are the UML-like class diagrams which I used:
||
| Tile |
||
||
| type: Type|
| x: int|
| y: int|
||
||
| + Tile(x: int, y: int, label: char): << constr >> |
| - assignType(label: char): void|
| + equals(o: Object): boolean |
| + hashCode(): int |
| + toString(): String|
||
||
| Type (enum)|
||
||
| - passable: boolean |
| - label: char|
||
||
| - Type(passable: boolean, label: char): << constr >> |
| + isPassable(): boolean|
| + toString(): String |
||
| |
| + Maze |
||
| |
| - tiles: Tile[][]|
| start: Tile |
||
| |
| + Maze(mazeData: String[]): << constr >>|
| + getNeighbours(center: Tile): List<Tile>|
| - processMazeData(mazeData: String[]): void |
| + toString(): String|
||
__
||
| + Path |
|__|
||
| tiles: List<Tile>|
|__|
||
| + Path(): << constr >>|
| + Path(tiles: List<Tile>): << constr >> |
| + add(tile: Tile): void|
| + toString(): String|
|__|
Good luck.
# 20
Hi,
Have you considered using D*? It is short for Dynamic A* and is used in situations where only parts of the map are known. I think it's been used for autonomous robot pathfinding from the Mars Rover to military applications and undersea searching.
I'm writing a Mars Rover simulation and I've used a slightly modified A* (I don't think it is really D*) algorithm. The algo. calculates the path from start to goal just as a normal A* would, except when it has to traverse an unknown map segment, it assumes that the path is flat terrain, free of obstacles. As the robot moves from its starting position along the calculated path, it checks to see if the next visible position is an obstacle (another robot or impassable terrain). If the next visible position is an obstacle, the robot recalculates the path to the goal from that position.
The advantage of this approach is that you combine the efficiency of A* with dynamic path selection, which is very important when dealing with what could be a fluid, fast changing environment .
I've found the following (pdf) articles useful and I've listed them in no particular order. Search for them on Google.
The Focussed D* Algorithm for Real-Time Replanning by Anthony Stentz
Cooperative Pathfinding by David Silver
Fringe Search: Beating A* at Pathfinding on Game Maps by Yngvi Bjornsson et al
Fast Replanning for Navigation in Unknown Terrain by Sven Koenig
Improved Fast Replanning for Robot Navigation in Unknown Terrain by Sven Koenig et al
Path Planning and Navigation of Mobile Robots
in Unknown Environments by Torvald Ersson et al
Distributed Coordination of Autonomous Agents by Communicating on a
Need-To-Know Basis by Judy Y. Chen
Distributed Area Search with a Team of Robots by Velin K. Tzanov
Have fun,
Has
