Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- -- See Benchmarks.txt for details on this test
- function performAStar(repetitions)
- map = [[S XXX X
- XX XXXXXXXXXXXXX X
- XX X
- X XXX XXXXXX
- XXXX XXXXXXXX
- XXXXXXX X X
- XX X XXXXX X
- XX XX X
- XXXXXXXXXXX X
- XX XXXXXXXXX X
- XXXXXX X
- X XXX XXXXXX
- XXXX XXXXXXXX
- XXXXXXX X X
- XX X XXXXX X
- XX XX X
- XXXXX XXXXX X
- XX XXXX XXXX X
- XXXXXX X
- X XXX XXXXXX
- XXXX XXXXXXXX
- XXXXX XX X X
- XX X XXXXX X
- XX XX X
- XXXXX XXXXXXXXXXXX X
- G XX X
- XXXXXXXXXXXXXXXXXXXXXXX]];
- for i=0,repetitions do
- nodes, start, goal = parseMap(map);
- if aStar(start, goal) then
- reconstructPath(goal);
- else
- io.write("No valid path found!");
- end
- end
- end
- function parseMap(map)
- local x = 1;
- local y = 1;
- local width=1;
- local height=1;
- local nodes = {};
- local start;
- local goal;
- -- create all nodes and find start and goal
- for i=1,#map do
- char = string.byte(map, i);
- if char == string.byte("\n") then -- linebreak?
- y = y+1;
- width = x-1;
- x = 1;
- else
- if nodes[x] == nil then
- nodes[x] = {};
- end
- if char ~= string.byte("X") then --accessible node?
- -- create a new node with the current coordinates
- local node = {};
- node.x = x;
- node.y = y;
- node.g = 1.0/0.0; -- initialize these values with infinity
- node.f = 1.0/0.0;
- node.neighbors = {};
- node.previous = nil;
- --check if this node is start or goal
- if char == string.byte("S") then
- start = node;
- elseif char == string.byte("G") then
- goal = node;
- end
- -- save the node in our list, indexed by its coordinates
- nodes[x][y] = node;
- end
- x = x+1;
- end
- end
- height = y;
- -- connect the nodes
- for x=1, width do
- for y=1, height do
- if nodes[x][y] ~= nil then
- -- up
- if y > 1 and nodes[x][y - 1] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x][y - 1]);
- end
- -- up right
- if y > 1 and x < width and nodes[x + 1][y - 1] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x + 1][y - 1]);
- end
- -- right
- if x < width and nodes [x + 1][y] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x + 1][y]);
- end
- -- right down
- if x < width and y < height and nodes[x + 1][y + 1] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x + 1][y + 1]);
- end
- -- down
- if y < height and nodes[x][y + 1] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x][y + 1]);
- end
- -- down left
- if y < height and x > 1 and nodes[x - 1][y + 1] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x - 1][y + 1]);
- end
- -- left
- if x > 1 and nodes[x - 1][y] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x - 1][y]);
- end
- -- left up
- if x > 1 and y > 1 and nodes[x - 1][y - 1] ~= nil then
- table.insert(nodes[x][y].neighbors, nodes[x - 1][y - 1]);
- end
- end
- end
- end
- return nodes, start, goal;
- end
- -- returns true iff there is a path between start and goal.
- -- the 'previous' value is set accordingly for each node on the path
- function aStar(start, goal)
- local closedSet = {};
- local openSet = { start };
- start.g = 0.0;
- start.f = h(start, goal);
- while #openSet > 0 do
- local current = findBest(openSet);
- table.insert(closedSet, current);
- if current == goal then
- return true;
- end
- for index,neighbor in next,current.neighbors,nil do
- if not hasNode(neighbor, closedSet) then
- local newG = current.g + h(current, neighbor);
- if newG < neighbor.g then
- neighbor.g = newG;
- neighbor.f = newG + h(neighbor, goal)
- neighbor.previous = current;
- end
- if not hasNode(neighbor, openSet) then
- table.insert(openSet, neighbor)
- end
- end
- end
- end
- return false;
- end
- --save the length of the result to prevent the compiler omptimizing away anything important
- resultLen = 0;
- -- pack the path saved in the nodes into a string
- function reconstructPath(goal)
- local pathString = "";
- node = goal;
- while node ~= nil do
- pathString = "("..(node.x)..","..(node.y)..")"..pathString;
- node = node.previous;
- end
- resultLen = #pathString;
- return pathString;
- end
- -- the heuristic used is simply the distance between the nodes
- function h(current, goal)
- local dx = current.x - goal.x;
- local dy = current.y - goal.y;
- return math.sqrt(dx*dx + dy*dy);
- end
- --search and remove the node with the best f value in a given set
- function findBest(nodes)
- local best = nil;
- local bestF = 1.0/0.0;
- local bestIndex = 0;
- for index,node in next,nodes,nil do
- if node.f < bestF then
- best = node;
- bestF = node.f;
- bestIndex = index;
- end
- end
- if best ~= nil then
- table.remove(nodes, bestIndex);
- end
- return best;
- end
- -- returns true iff haystack contains needle
- function hasNode(needle, haystack)
- for index,node in next,haystack,nil do
- if node == needle then
- return true;
- end
- end
- return false;
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement