astar to slow to work with... doing it wrong I guess

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
gcmartijn
Party member
Posts: 134
Joined: Sat Dec 28, 2019 6:35 pm

astar to slow to work with... doing it wrong I guess

Post by gcmartijn »

Hi,

After several weekends I give up, and need some advice for next weekend.
I want that a player can walk around a rectangle if he is clicking above/below/right/left so the player would walk around it automaticly (if needed).

I have several functions like willCollide(x,y)

The world only have rectangles at the moment AABB (and I have polygon data).
The basic collision system is working good enough.

I did try to solve this without Astar but that din't go well, so before going to bed I though let's try AStar.
https://github.com/wesleywerner/lua-star

I did modify it a little so it can handle my Player: positionIsOpenFunc [self] (self.map)

Code: Select all

function Player:positionIsOpenFunc(x, y)
    return self.map[x][y]
end

function Player:createMap(targetX, targetY)
    local width = 2048 -- this is going to be bigger
    local height = 768

    -- the default map everything is walkable
    self.map = {}
    for x = 1, width do
        self.map[x] = {}
        for y = 1, height do
            self.map[x][y] = true
        end
    end

    for _, set in pairs(self.framesetsToCheckCollision) do
        local frame = set:getCurrentFrame()
        for y = frame.quad.h, frame.y do
            for x = frame.x, frame.quad.w do
                self.map[x][y] = false
            end
        end
    end

    local currentX = self.activeFrameset:getX()
    local currentY = self.activeFrameset:getY()

    print("check")
    -- ^^^^^^^^^^ everything is fast above this line
    
   -- local path =
   --     Astar:find(
   --     width,
   --     height,
   --     {x = math.floor(currentX), y = math.floor(currentY)},
   --     {x = math.floor(targetX), y = math.floor(targetY)},
   --     self,
   --     false
   -- )
   -- if path then
    --    print("yes")
    ---- for _, p in ipairs(path) do
    ----     print(p.x, p.y)
    ---- end
   -- end
end
When I uncomment the Astar code the game will crash because it is super slow.

- Do I need astar to walk around rectangles ?
- Can astar handle bigger maps ?
- Is this the correct way to use astar ?

Thanks for the info
User avatar
ReFreezed
Party member
Posts: 612
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

Re: astar to slow to work with... doing it wrong I guess

Post by ReFreezed »

It looks like you're giving Astar:find() the wrong value for the positionIsOpenFunc argument. It's supposed to be a function - not a table ('self' in this case). Unless you modified the library to correctly handle that? Impossible to tell if you don't share the code.

A grid of size 2048x768 does seem very big - at least if large areas are walkable. You can use print(collectgarbage("count")) to see how much memory is being used. Maybe put that code in Player:positionIsOpenFunc() to see if it's actually the memory usage that is causing the crash.

Is your game actually grid based? The A* search algorithm does not require an axis-aligned grid to work - only a set of nodes that are connected. (On a grid, every square is a "node".) So if your game isn't grid-based then it's probably better to have fewer strategically placed nodes in the game world and let A* operate on them. (You'll need to modify that library more for that to work). For example, have a node in every corner of every obstacle, and maybe a node for the player and the "target", and connect all nodes that can "see" each other (they would be the "neighbors", in A* terms).

A* is very useful, and the algorithm is not very complicated. I think it's a good idea for any game developer to try to understand how it works. The pseudocode in the Wikipedia article is a good place to start, I think.
Tools: Hot Particles, LuaPreprocess, InputField, (more) Games: Momento Temporis
"If each mistake being made is a new one, then progress is being made."
gcmartijn
Party member
Posts: 134
Joined: Sat Dec 28, 2019 6:35 pm

Re: astar to slow to work with... doing it wrong I guess

Post by gcmartijn »

It looks like you're giving Astar:find() the wrong value for the positionIsOpenFunc argument. It's supposed to be a function - not a table ('self' in this case). Unless you modified the library to correctly handle that? Impossible to tell if you don't share the code.
That is a quick modification so I can see if astar is working.
It contains a table (self) object, that includes the self.map

If I undo that its is still slow, that is not the problem, the map is to big I guess.

Code: Select all

function Player:positionIsOpenFunc(x, y)
    return self.map[x][y]
    --         ^ 
end
No the game is not grid based, it is an open world like you watch a cartoon, point and click adventure.
In that world there are only rects, and however the player can walk around rects manual , I though maybe I can help the player by doing this automatically.

Maybe I will skip this part for now, it cost me too much time at the moment.
monolifed
Party member
Posts: 188
Joined: Sat Feb 06, 2016 9:42 pm

Re: astar to slow to work with... doing it wrong I guess

Post by monolifed »

https://github.com/monolifed/lua-modules -> astar
Since all the others was not really simple, I made this. It may help

A note: returned path is from destination to start
Last edited by monolifed on Tue Jun 08, 2021 7:27 am, edited 2 times in total.
gcmartijn
Party member
Posts: 134
Joined: Sat Dec 28, 2019 6:35 pm

Re: astar to slow to work with... doing it wrong I guess

Post by gcmartijn »

I did give it a try, but it is too big and a little complicated (for me) to understand/merge with my own code.
Maybe if everything was inside one class and I can add the map data into it, then it is more user friendly.

I put this on hold for now.

Code: Select all

function Player:createMap(targetX, targetY)
    local width = 2048
    local height = 768

    -- the default map everything is walkable
    self.map = {}
    for y = 0, height - 1 do
        local row = {}
        for x = 0, width - 1 do
            row[x] = 0 -- cost 0 ??
        end
        self.map[y] = row
    end

    for _, set in pairs(self.framesetsToCheckCollision) do
        local frame = set:getCurrentFrame()

        for y = frame.quad.h, frame.y do
            for x = frame.x, frame.quad.w do
                self.map[y][x] = 1 -- cost 1 ?
            end
        end
    end

    self.astar = Astar.astar.new(self.map, Astar.neighbors8, Astar.distance8, Astar.heuristic8)

    local currentX = math.floor(self.activeFrameset:getX())
    local currentY = math.floor(self.activeFrameset:getY())

    local startcost = mapget(self.map, currentX, currentY)
    local goalcost = mapget(self.map, math.floor(targetX), math.floor(targetY))

    print("check", startcost, goalcost)

    local time = 0 -- average path finding time
    local repeatcount = 100 -- (average) time = totaltime / repeatcount

    local numvisited, pathcost, costmap = 0, 0, nil
    if startcost and goalcost then
        time = love.timer.getTime()
        for i = 1, repeatcount do
            costmap = {}
            local start = Astar.setcost(currentX, currentY, startcost, costmap)
            local goal = Astar.setcost(math.floor(targetX), math.floor(targetY), goalcost, costmap)
            mappath, pathcost = self.astar:find(start, goal)
        end
        time = ((love.timer.getTime() - time) * 1000) / repeatcount
        numvisited = numvisited / repeatcount
        if mappath then
            print("yes")
        -- mappath.polyline = path2polyline(mappath)
        end
    else
        mappath = nil
    end
end
The problem now is

Code: Select all

local neighbors8 = function(context, node)
    -- It is likely that we don't need to check this with A*
    if node.neighbors then
        return node.neighbors
    end

    local x, y = node.x, node.y
    local rt, rc, rb = mapdata[y - 1], mapdata[y], mapdata[y + 1]
---------------------------^ attempt to index global 'mapdata' (a nil value)
That mapdata is self.map in a object in my code (only working with objects).
gcmartijn
Party member
Posts: 134
Joined: Sat Dec 28, 2019 6:35 pm

Re: astar to slow to work with... doing it wrong I guess

Post by gcmartijn »

I found one other astar script, maybe he know the answer because it is drawing lines very fast, only not correct...
So I asked the question there: https://github.com/xiejiangzhi/astar/issues/1
Post Reply

Who is online

Users browsing this forum: No registered users and 40 guests