Need A* Help

[Zilarrezko]

Alright, since no one really responded at my last post about A* I made little to no progress trying to implement someone else's astar library. I decided to just go ahead and write my own yet add jump point search later and of course I'm having trouble basically right off the bat trying to follow this tutorial. http://www.policyalmanac.org/games/aStarTutorial.htm

This has two possible questions that you can answer, on or the other or both if you've got balls of steel.

Here's the problem, I'm doing astar so I have to get the neighbors to a tile. And that's what I'm having trouble with.

One: How do I use multidimensional arrays in the case of creating tiles through OOP and adding them to a multidimensional array and use that multidimensional array to check for the neighboring tiles (including the diagonals), although I have I believe I have a pretty good idea on checking the neighbors once I get the multidimensional array of tiles. (when I say multidimensional array, I mean two dimensional 'tileList[x][y]')

Two: An alternative way of checking for neighboring tiles (of course, including the diagonals) using a normal array, filled with tiles that are tables.

I hope someone responds to this one, otherwise I don't know where to go at this point. Keep rockin', and obey.

[Roland_Yonaba]

Hi Zilarrezko.

May I ask a question first. Not that I am saying "don't reinvent the wheel", but for what purposes ar you trying to implement someone else's Astar library ? Why not use some already working library ? There are tons of implementations out there.
But, if you just want to write your own Astar, for learning purposes, well, then I can provide a bit of help. Actually, Patrick Lester's tutorial is a very good one (maybe the best) on explaining Astar's logic. Maybe you should try to implement a simple case and get it to work, first. Then, you can design and implement your own library from it.

[Zilarrezko]

I think you were the one that actually made an a star and jump point search on love, tried to run it but it was outdated. Like I said in the first post I tried to implement https://github.com/lattejed/a-star-lua although I couldn't get the algorithm to path around tiles with a collision Boolean.

Are you suggesting I look for one on the forum? As I tried and only found your stuff I believe. I tried to find something working, but I haven't had any luck. And yes I am trying to learn by having the code and understanding it so I can later implement it, always learning always coding, cause I obey.

[zorfmorf]

I'd love to help but but your description seems a bit vague. Are you having trouble getting your code to run or don't you know where to start? Do you have any existing code that you want to add on to or are you starting from scratch?

One: How do I use multidimensional arrays in the case of creating tiles through OOP and adding them to a multidimensional array and use that multidimensional array to check for the neighboring tiles (including the diagonals), although I have I believe I have a pretty good idea on checking the neighbors once I get the multidimensional array of tiles. (when I say multidimensional array, I mean two dimensional 'tileList[x][y]')

So you want to implement the A* path finding algorithm. Your tiles are oop objects and they are saved in a two-dimensional array? Or are you trying to convert them into a 2d-array and can't figure out how?

Two: An alternative way of checking for neighboring tiles (of course, including the diagonals) using a normal array, filled with tiles that are tables.

So your tiles are saved in a one-dimensional array and you want to test for neighbours? Assuming your tiles have coordinates you could go through all tiles and check their coordinates to find neighbours, but that's definitely not what you want as it is a very inefficient way of doing this.

Again it would really help if you could post your code or at least the way your tiles are currently set up - otherwise it's hard to help.

[Zilarrezko]

I asked for help outside of Love2D and I think I might be able to do it. I just had trouble getting a my tiles which are tables into a 2D array, because I didn't know how to do multidimensional arrays. But not I have a basic understanding and I'll get back to everyone on this.

Edit: but thank you for responding at least hahaha

[Zilarrezko]

Alright, so I got to the point of getting to check a node to see if the player is on the node and make that the starting node. Then I believe I successfully made all adjacent nodes' parent to be that starting node. I'm now stuck on contemplating how to go about calculating the g and h costs on a nodes' parent.

I was thinking of using the Manhattan heuristic method, but in the future I want to make this algorithm into a jump point search, as it seems to be faster and better.

It's hard to see, but I managed to create nodes at every tile that doesn't have a self.collide = true Boolean.

And if it matters at all I wanted the player (or square) to move independent of the tiles.

I also foresee a problem that the player will try to clip corners since I want the player to move diagonally (does this make sense? I mean the player will run into a corner of a collidable tile trying to move from one node to another diagonally.)

Basically I'm starting to get lost on how to do this stuff. I could recite almost every step of the A* calculation process on paper. I'm having a lot of trouble transferring it onto Lua.

I hope this makes sense, yet somehow only about 10% of anything I say make sense to anybody. I guess that's just because talking code is confusing.

hint: left click to create/destroy collidable tile

edit: that was probably stupid of me to say manhattan heuristic, as I wanted diagonals. and manhattan is rows and columns haha. my bad...

[zorfmorf]

Okay I took a look at your code. First: Don't get hung up on details. It does not matter for now how the player will move on the path you find with A* and you should not try to account for that in your implementation. The only thing you want to do is calculate a path to the target on squares that are empty. How the player travels on that path is another matter that you can think about once you have that path. So I'd recommend to focus on implementing A* (and maybe drawing the resulting path on the screen which makes debugging much easier).

In addition you could make your life a whole lot easier if you dropped either your nodes or your map list. Currently you basically have two data structures that represent you grid, the map and the nodes list and they differ in structure. I'd try to merge them into one construct.

The link you posted does seem to do a good job of explaining A*. However, in your pathfind:calculate(goal) method, you seem to be doing something completely different. I'd recommend to focus on the 'Summary of the A* Method' section and follow it step by step. Save your generated path somewhere and add a draw method that draws the path if it exists. Don't worry about moving the player on that path for now.

Based on your exisiting code I started rewriting your calculate-method to show you how you'd start. Just follow the step-by-step instructions in your guide from there on.

Code: Select all

function pathfind:calculate(goal)
    
    -- 1) Add the starting square (or node) to the open list.
    for i=1,#nodes do
        for j=1,#nodes[i] do
            if nodes[i][j].x <= player.x and player.x < nodes[i][j].x + 16 and
                nodes[i][j].y <= player.y and player.y < nodes[i][j].y + 16 then
                
                nodes[i][j].cost = 0 -- because we start on this one
                table.insert(pathfind.open, nodes[i][j])
                i = #nodes + 1
                break
            end
        end
    end
    
    --2) Repeat the following:
    while #pathfind.open > 0 do
        
        -- a) Look for the lowest F cost square on the open list. We refer to this as the current square.
        local currentNodeId = 1
        for i=1,#pathfind.open do
            if pathfind.open[i].cost < pathfind.open[currentNodeId].cost then
                currentNodeId = i
            end
        end
        
        -- b) Switch it to the closed list.
        local currentNode = table.remove(pathfind.open, currentNodeId)
        table.insert(pathfind.closed, currentNode)
        
        -- c) For each of the 8 squares adjacent to this current square …
        
        ...
    end

end

I hope this helps. If not, don't hesitate to ask!

Edit: I expanded on the example to include cost handling!
Whenever you add a node to the openList, you have to set it's cost value, which is just currentNode.cost + 1

[Zilarrezko]

sorry I'm terrible at looking at code and figuring out whats going on.

1)So... how am I suppose to find the adjacent nodes from the current node? I'm trying to figure out what to use to get that started since some stuff was changed.

2)And the reason I was using nodes is I thought it would off the bat since I don't put a node in the middle of a tile if the tile is collidable. Should I really just use map tiles and get rid of nodes?

3)Wouldn't the cost when adding the starting node be the gcost? I noticed that in the while loop you were talking about lowest fcost yet you just used nodes[j].cost. In which case wouldn't it always choose the starting node since it's cost variable is 0?

4)Another thing is I'm curious as to what this does.

Code: Select all

for i=1, #nodes do
		for j=1, #nodes[i] do
			if boxCollision(player.x, player.y, player.w, player.h, nodes[i][j].x, nodes[i][j].y, 16, 16) then
				nodes[i][j].gcost = 0 -- because we start on this one
				nodes[i][j].hcost = pathfind:h_cost(nodes[i][j], goal)
				nodes[i][j].fcost = nodes[i][j].gcost + nodes[i][j].hcost
				table.insert(pathfind.open, nodes[i][j])
				i = #nodes + 1 <-------------- this thing, what is it doing?
				break
			end
		end
	end

and it seems that your checking for if the player was on the node didn't work and so that made it that it never inserted the node to the open list, and then never entered the while loop. So I put in the box collision function that's handy dandy

so here's what I have so far...
I added when we found our starting node, I added a gcost hcost and fcost.
I added a debugging thing cause at first I had no idea what some of the stuff was returning and the like (never knew table.remove returned the removed table, which is interesting)

Code: Select all

pathfind= {}
pathfind.open = {}
pathfind.closed = {}
local nodes = {}

function pathfind:generateNodes()
	for i = 1, #nodes do
		table.remove(nodes)
	end
	for i = 1, #map do
		nodes[i] = {}
		for j = 1, #map[i] do
			if not map[i][j].collide then
				nodes[i][j] = {
					x = map[i][j].x + 16,
					y = map[i][j].y + 16
				}
			end
		end
	end
end

function pathfind:drawNodes()
	gr.setColor(0, 0, 255, 255)
	for i = 1, #nodes do
		for j = 1, #nodes[i] do
			if nodes[i][j] then
				gr.point(nodes[i][j].x, nodes[i][j].y)
			end
		end
	end
end

function pathfind:drawPath()
end

function pathfind:calculate(goal)
    
	-- 1) Add the starting square (or node) to the open list.
	for i=1, #nodes do
		for j=1, #nodes[i] do
			if boxCollision(player.x, player.y, player.w, player.h, nodes[i][j].x, nodes[i][j].y, 16, 16) then
				
				nodes[i][j].gcost = 0 -- because we start on this one
				nodes[i][j].hcost = pathfind:h_cost(nodes[i][j], goal)
				nodes[i][j].fcost = nodes[i][j].gcost + nodes[i][j].hcost
				table.insert(pathfind.open, nodes[i][j])
				i = #nodes + 1
				break
			end
		end
	end
	
    --2) Repeat the following:
	while #pathfind.open > 0 do
        
		-- a) Look for the lowest F cost square on the open list. We refer to this as the current square.
		local currentNodeId = 1
		
		for i = 1, #pathfind.open do
          if pathfind.open[i].fcost < pathfind.open[currentNodeId].fcost then
				currentNodeId = i
          end
		end
        
       -- b) Switch it to the closed list.
       local currentNode = table.remove(pathfind.open, currentNodeId)
       table.insert(pathfind.closed, currentNode)
        
        -- c) For each of the 8 squares adjacent to this current square …
	end
end

function pathfind:h_cost(current, goal)
	return distV(current, goal)
end

function pathfind:g_cost(current, parent)
	return current.gcost + parent.gcost
end

function pathfind:keypressed(key, uni)

end

function pathfind:debuger()
	print("Closed List:")
	for k, v in ipairs(pathfind.closed) do
		for i, j in pairs(v) do
			print(i, j)
		end
	end
	print("Open List:")
	for k, v in ipairs(pathfind.open) do
		for i, j in pairs(v) do
			print(i, j)
		end
	end
end

Sorry that was a lot.

[ArchAngel075]

Im not sure if you are aiming to build the library yourself(as a project or needed for improved feature support) but if its of any use I found and have started using the following a-star library in conjunction with STI and have had very good results.
Running a path find to the same target from same location every tick on a 32x32 map is painfully slow, but then again why would you do it so often.
Running every time a "order" is issued to one of my units on the same map creates no lag at all.

anyways here is the wonderful a-star library i am using : https://github.com/lattejed/a-star-lua/ ... a-star.lua

[Zilarrezko]

Tried it, but had a trouble sum time implementing it. Couldn't figure out how to get it to recognize that a node with node.collide was not a valid node. tried a lot of stuff but, no one responded to that post. So I made this post to try and get things squared away with troubles of transferring the concept to code.