## 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
gcmartijn
Prole
Posts: 35
Joined: Sat Dec 28, 2019 6:35 pm

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

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

ReFreezed
Party member
Posts: 204
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

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

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, (more)
Games: Momento Temporis: Light from the Deep, Energize!
"If each mistake being made is a new one, then progress is being made."

gcmartijn
Prole
Posts: 35
Joined: Sat Dec 28, 2019 6:35 pm

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

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: 139
Joined: Sat Feb 06, 2016 9:42 pm

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

https://github.com/monolifed/luvarc -> 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 Sun Dec 06, 2020 10:11 am, edited 1 time in total.

gcmartijn
Prole
Posts: 35
Joined: Sat Dec 28, 2019 6:35 pm

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

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
Prole
Posts: 35
Joined: Sat Dec 28, 2019 6:35 pm

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

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

### Who is online

Users browsing this forum: Google [Bot] and 55 guests