Jump to content
  • Advertisement
Sign in to follow this  
KaiserJohan

some a* questions

This topic is 996 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

1. I've been able to build smaller test sets (~20 * ~20) manually like this:

s = start
f = goal
1 = passable
0 = impassable

f, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1,
1, 0, s, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1,
1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

But constructing large sets (like 1000 * 1000) by hand is not feasible. Are there any tools or available test files available one can use to test ones implementation of a* alghorithm?

 

 

2. Reading the pseudo-code on wiki:

function A*(start, goal)
    // The set of nodes already evaluated.
    closedSet := {}
    // The set of currently discovered nodes still to be evaluated.
    // Initially, only the start node is known.
    openSet := {start}
    // For each node, which node it can most efficiently be reached from.
    // If a node can be reached from many nodes, cameFrom will eventually contain the
    // most efficient previous step.
    cameFrom := the empty map

    // For each node, the cost of getting from the start node to that node.
    gScore := map with default value of Infinity
    // The cost of going from start to start is zero.
    gScore[start] := 0 
    // For each node, the total cost of getting from the start node to the goal
    // by passing by that node. That value is partly known, partly heuristic.
    fScore := map with default value of Infinity
    // For the first node, that value is completely heuristic.
    fScore[start] := heuristic_cost_estimate(start, goal)

    while openSet is not empty
        current := the node in openSet having the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, goal)

        openSet.Remove(current)
        closedSet.Add(current)
        for each neighbor of current
            if neighbor in closedSet
                continue		// Ignore the neighbor which is already evaluated.
            // The distance from start to goal passing through current and the neighbor.
            tentative_gScore := gScore[current] + dist_between(current, neighbor)
            if neighbor not in openSet	// Discover a new node
                openSet.Add(neighbor)
            else if tentative_gScore >= gScore[neighbor]
                continue		// This is not a better path.

            // This path is the best until now. Record it!
            cameFrom[neighbor] := current
            gScore[neighbor] := tentative_gScore
            fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)

    return failure

function reconstruct_path(cameFrom, current)
    total_path := [current]
    while current in cameFrom.Keys:
        current := cameFrom[current]
        total_path.append(current)
    return total_path

In my case, as in the layout I showed in #1, the distance between a node and its neighbours are always 1 (adjacent). The "gScore" always increases by one each step away from start node.

Dosn't that mean that mean I can simplify it so whenever we add a node we have the optimal path between the start node and it

 

So either the node is in the open or closed set and we ignore it or its not visited and we add it, like below:

function A*(start, goal)
        ...
        for each neighbor of current
            if neighbor in closedSet or openSet
                continue
            
            openSet.Add(neighbor)
            cameFrom[neighbor] := current
            gScore[neighbor] := gScore[current] + 1
            fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
        ...

Edited by KaiserJohan

Share this post


Link to post
Share on other sites
Advertisement
I'd drop all the ", " stuff in your data file, and use better characters than 0 and 1 (they're visually hard to distinguish). You might end up with something like
.....@....#.............#.........................
..........#.............##........................
..........#..............#........................
..........#.......................................
.....#################..#########.###########.....
.....................#...............#......##....
.....................#...............#....*..#....
.....................................#.......##...
.....................#...............#...#....#...
.....................#.......#.......#...#........
.....................#.......#.......#...#....#...
which you can just save as a .txt file, where you read it line-based.
 
This scales up to about 100x100 quite easily, you can use your favorite text editor to modify the layout.
My tests are always about the algorithm itself, where such sizes are sufficient.
 
For bigger maps, you can switch to eg black/white images that you read. Not sure what you want to test here however. Edited by Alberth

Share this post


Link to post
Share on other sites

write a routine to randomly generate test maps.

 

declare a 2d array

set it all to "passable"

then loop some number of times, switching random locations from "passable" to impassable.

or loop through the map, with a random chance to set each square to impassable.

you can also loop top to bottom, setting the left and right edges to impassable, and similarly for looping left to right and closing off the top and bottom, to enclose the entire search area.

as a final step, you can also generate random start and goal points - perhaps at a random location along a random edge..

 

you can also do it by staring with everything impassable, then doing "passable" splotches of random size areas at random locations. or lines/corridors/halls of randomly placed runs of "passable" in random directions of a random length.  finish by closing off the edges and setting start and goal points.  this is a more "carve it out" vs "add it in" approach to generating maps.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

Yeah, for my purposes, doing as Norman suggests is all I did.  Random chance of blocking a tile.  It's by no means perfect, but it worked for me.  If you're a more corridor style game, you may want to look into generating maps that way to test your pathfinding.  Though if you're doing A* that part doesn't matter, unless you start adding cooperative components or want to deal with blocking/obstacle avoidance, etc, and then you'd need it.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!