Trying to make A* pathfinding

Help and Feedback Scripting Support
#21

I have got only one question. How do I change the parenthesis in the GetNeighbors function?

1 Like
#22

I’m not quite sure what you mean here.

Also sorry. Totally forgot I was going to look into that more.

1 Like
#23

The value in brackets for function seem to be called “Parenthesis”. If not wrong, when making a local function, the “Parenthesis” is just name for some object or value, but when we call for function, we replace that with the value we want:

local function Mathematics(a, b) -- a and b are both parenthesis in this scenario
     local result = a - b
     return result
end


-- calling function

print(Mathematics(10, 6)) -- parenthesis is replaced for what we want

-- result for print should be 4

But I actually thought of this, and it seems that I can just make a local like “upcoming”, and change the instance for that local at the end of each iteration. Did not test it yet, but going to soon.

In idea is it is something like that:

local upcoming == ___ -- Some node

local function GetNeighbors(center)
-- code, bla bla bla, code
end

GetNeighbors(upcoming)

Did I understand it right, and would that even work?

1 Like
#24

Ahh. I think the term you mean is parameter. In this case yes, “center” is a parameter for the function. So getNeighbors returns a list of neighbors for any node you pass in (the naming I chose could have been more clear, but I was trying to keep some of your variable names to make the relationship between my code and yours more direct).

In this case the parameter is meant to be the cheapest node in the openList that gets passed in since that’s the one you are checking each time.

So as we loop we get what we assume is the cheapest node. We pull that from the open list. Get it’s neighbors (getNeighbor(currentNode)) and loop through each of those neighbors adding them to the open list if they don’t already exist (or update them if they do). Finally checking to see if the finish is in the open list and generate the path from that.

1 Like
#25

Yeah, so I guess my example should work?

2 Likes
#26

I believe so. Yes.

(Message length requirements).

2 Likes
#27

Ok then, I will now attempt to make another one version of code with all the new data. Hope I can post it later today, thanks again for your help.

2 Likes
#28

I made a new version which is quite successful. However, I ran into an issue. It seems that for some reason, only one part is being added into the “neighborsList”, even though it used to put more before. I don’t really know why this happens. Other than getting surrounded by “lockedList” parts eventually, it works pretty well. Here is the code:

local active = false

local finish = workspace.Nodes.Finish
local start = workspace.Nodes.Start

local upComing

local Nodes = workspace.Nodes:GetChildren()
local openList = {}
local closedList = {}


local function GetNeighbors(Center) -- Get neighbors of current node, AKA upcoming
	
	local neighbors = {}
	
	for i, node in pairs(Nodes) do
		if math.abs(node.Position.X / 8) == math.abs(Center.Position.X / 8) and math.abs(node.Position.Z / 8) == math.abs(Center.Position.Z / 8) + 1 then
			table.insert(neighbors, node)
		elseif math.abs(node.Position.X / 8) == math.abs(Center.Position.X / 8) and math.abs(node.Position.Z / 8) == math.abs(Center.Position.Z / 8) - 1 then
			table.insert(neighbors, node)
		elseif math.abs(node.Position.X / 8) == math.abs(Center.Position.X / 8) + 1 and math.abs(node.Position.Z / 8) == math.abs(Center.Position.Z / 8) then
			table.insert(neighbors, node)
		elseif math.abs(node.Position.X / 8) == math.abs(Center.Position.X / 8) - 1 and math.abs(node.Position.Z / 8) == math.abs(Center.Position.Z / 8) then
			table.insert(neighbors, node)
		end
	end
	
	return neighbors 
	
end

local function UpdateNeighbors(Center, Neighbors) -- Detect if neighbors are occupied or already in openList
	for i, neighbor in pairs(Neighbors) do
		if table.find(closedList, neighbor) then continue end
		if table.find(openList, neighbor) then
			if neighbor:GetAttribute("MoveCost") == not 0 and neighbor:GetAttribute("MoveCost") < Center:GetAttribute("MoveCost") + 1 then
				continue
			end
		end
		
		local mCost = Center:GetAttribute("MoveCost") + 1
		neighbor:SetAttribute("MoveCost", mCost)
		
		local hCost = math.abs(finish.Position.X / 8 - neighbor.Position.X / 8) + math.abs(finish.Position.Z / 8 - neighbor.Position.Z / 8)
		neighbor:SetAttribute("TotalCost", mCost + hCost)
		
		neighbor:SetAttribute("CameFrom", Center.CFrame)
		
		table.insert(openList, neighbor)
		
		table.remove(openList, table.find(openList, Center))
		table.insert(closedList, Center)
		
	end
end

local function UpdateNodes() -- Update nodes: Their color and list references
	for i, node in pairs(Nodes) do
		if node:GetAttribute("Occupied") == true and table.find(closedList, node) then
			continue
		elseif node:GetAttribute("Occupied") == true and not table.find(closedList, node) then
			table.insert(closedList, node)
		end
		
		if table.find(closedList, node) and node:GetAttribute("Occupied") == true then
			node.Color = Color3.fromRGB(60, 0, 0)
		elseif table.find(closedList, node) and node:GetAttribute("Occupied") == false then
			node.Color = Color3.fromRGB(60, 60, 60)
		elseif table.find(openList, node) then
			node.Color = Color3.fromRGB(0, 180, 240)
		end	
	end
end

local function GetUpcoming() -- Get best part for the next iteration
	
	local Costs = {}
	
	for i, node in pairs(openList) do
		local tCost = node:GetAttribute("TotalCost")
		table.insert(Costs, tCost)
	end
	
	local bestCost = math.min(unpack(Costs))
	
	for i, node in pairs(openList) do
		if node:GetAttribute("TotalCost") == bestCost then
			upComing = node
			break
		else 
			continue
		end
	end
	
	return upComing
end

local function Cycle()
	repeat
		UpdateNodes()
		task.wait(1)
		UpdateNeighbors(upComing, GetNeighbors(upComing))
		task.wait(1)
		GetUpcoming()
		print(GetUpcoming())
	until table.find(openList, finish)
end

script.Parent.MouseClick:Connect(function()
	table.insert(openList, start)
	upComing = start
	
	Cycle()
end)

FIXED

1 Like
#29

Dude, I finally managed to make somewhat working! Look at that!
image
I will drop you the copy of the place so you can see for yourself, the process is quite satisfying!

2 Likes
#30

image
Just added some decals and scaled the nodes for cooler visualisation.

2 Likes
#31

That’s awesome! I’m glad you got it working.

2 Likes
#32

I am gonna try to develop the place with this algorithm. First I am currently trying to make some sort of a computer, on which player can choose their own field size. Then I am gonna add a tool that would choose the regular tiles to walls, and walls to tiles. Overall, as of now figuring out how buttons work, and made some sort of 2 working pages.

Main menu:

image
image736×398 67 KB

Edit menu:
image

Once everything works, I will probably make place public.

2 Likes
#33

Made this trowel tool, that allows to change state of a part between a wall or regular tile. Gonna make 2 other tools, AKA flags for start and finish, to mark the corresponding tiles. Generating menu is also almost done, having just slight issues with remote events.

image

image
image1120×834 220 KB

2 Likes
#34

In theory, the game is ready to be released. The main functions work well, except the button. ClickDetectors and Tools seem to be confronting, and the button is just not pressed after interacting with tool, so I had to replace click detector with proximity prompt. I also didn’t finalize function for random size generation, and currently adjusting tools functions.

2 Likes
#35

I fixed click detector and tools issue. Just had to unbind action before deleting tool.

#36

I think it is ready for the first test. I made the main functions of the game work properly. There might be still some issues that I did not think about. 1 button, “Random”, does not work as well because it is not as necessary as others, so I did not touch it yet. All the other buttons should work. Game link:

#37

I guess that is it for now. Really like what I came out with, learned lots of new stuff. I probably will give solution to tlr22 because he helped me the most.

1 Like
#38

This topic was automatically closed 14 days after the last reply. New replies are no longer allowed.