Naive Lua AStar

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