Trying to combine 2 types of loops?

[hinkalka230 (Greg)]

I am trying to make a Dijkstra algorithm. The way I wanted it to work is to get the surrounding parts for a specific amount of times. Lets say an entity has a range of 3 tiles. The algorithm would get the neighbors of the entity, putting them in a table called “openList”, and removing starting tile from it afterwards. Then, the newly added 4 nodes would go through same process one by one. The processed tiles/nodes would be put into a closed list. This image might show how I want the things to work, the tiles of same number kind of form a ring or a rectangle that gets progressively bigger:

To make this work I made this script:

local Nodes 

local openList = {}
local closedList = {}

local range = 3

local Start

local function GetNeighbors()
	
	local neighbors = {}
	
	for i, center in pairs(openList) do
		for i, node in pairs(Nodes) do
			if node.Position.X / 8 == center.Position.X / 8 and node.Position.Z / 8 + 1 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 == center.Position.X / 8 and node.Position.Z / 8 - 1 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 + 1 == center.Position.X / 8 and node.Position.Z / 8 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 - 1 == center.Position.X / 8 and node.Position.Z / 8 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			end
		end
		
		table.insert(closedList, center)
		table.remove(openList, table.find(openList, center))
		
		return neighbors
		
	end	
end

local function CheckNeighbors(neighbors)
	for i, node in pairs(neighbors) do
		if not table.find(openList, node) and not table.find(closedList, node) then
			table.insert(openList, node)
		end
	end
end

local function UpdateColor()
	for i, node in pairs(openList) do
		node.Color = Color3.fromRGB(0, 170, 255)
	end
	for i, node in pairs(closedList) do
		node.Color = Color3.fromRGB(45, 45, 45)
	end
end
script.Parent.MouseClick:Connect(function()
	Nodes = workspace:WaitForChild("Nodes"):GetChildren()
	Start = workspace:WaitForChild("Nodes").Start
	
	table.insert(openList, Start)
	
	for count = 0, range, 1 do
		UpdateColor()
		CheckNeighbors(GetNeighbors())
	end
	
	
	print(openList)
end)

It works relatively right, but it seems that “for count = … , … , … do” loop is conflicting with “for i, … in pairs(…)” loop. Instead of repeating the process 3 times, it kind of gets just 3 neighbors, resulting in this:

I was wondering if there is an alternative to my method. May be there is a method for “repeat” that would repeat the function for specific amount of times?

[Wigglyaa]

I think the GetNeighbours function is returning too early (after only one step in the iteration).

[jellolemo]

No way!

This is what I even been working on for a year and i didnt even know there was a name for it!

The only way I did it was more physical, so I have chunks stored in replicatedstorage that each have 4 neighbours and a chunkdatamodule that tells whats supposed to generate on each neighbour. I also codes it so it can generate multiple sized chunkmodels, so not only 1x1, but a combination of 1x1 and 2x1 and so on.

[hinkalka230 (Greg)]

Forum is a place to find such things. Really cool coincidance!

[hinkalka230 (Greg)]

The thing is, it probably does that because it is limited by the count function.

I think this way, because the more you add to range, the more nodes are being processed.

Ths is range + 1 for example

[hinkalka230 (Greg)]

I might try it. Just haven’t heard of it before.

[Wigglyaa]

Sorry, I mean literally, move the return statement outside the loop in the GetNeighbours function. Currently it is inside the loop meaning it will return at the end of the first iteration and not run through the others.

[hinkalka230 (Greg)]

It did work but not entirely. Probably issue with my code though, I’ll dig further into it.

[GodLikesYou (john)]

local function A(n) -- fill surrounding tiles that aren't searched yet if n == 0 then return end A(n-1) end

the structure would look something like this

[GodLikesYou (john)]

also i deleted the comment cause i thought you already were using it, but yeah using recursion makes sense here

[Wigglyaa]

Yes, I just noticed you were removing table elements from a table you were currently iterating over. Dynamic removals like this shifts elements causing the loop to ‘skip’.
When removing table elements during a loop you can either iterate in reverse (for #t, 1, -1 do) using t[i] to get the element and remove as you go meaning any shifts won’t affect the positions still to iterate over. Or, you can iterate as normal but mark them to be removed later, there are different ways to do this but as an example:

local function GetNeighbors()
	
	local neighbors = {}
        local markedForRemoval = {} --temporary table to hold references 
	
	for i, center in openList do
		for i, node in Nodes do
			if node.Position.X / 8 == center.Position.X / 8 and node.Position.Z / 8 + 1 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 == center.Position.X / 8 and node.Position.Z / 8 - 1 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 + 1 == center.Position.X / 8 and node.Position.Z / 8 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 - 1 == center.Position.X / 8 and node.Position.Z / 8 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			end
		end
		
		table.insert(closedList, center)
		table.insert(markedForRemoval, i) --insert position to remove
	end
       table.sort(markedForRemoval, function(a,b) return a > b end) --sort descending
       for i, v in markedForRemoval do --remove from table
            table.remove(openList, v)
        end
	return neighbors
end

[hinkalka230 (Greg)]

Ah yes, that is probably the issue. I honestly don’t know how I fell for it twice, as I literally thought of this before when making A* algorithm.

Yes this totally worked, but I just did slightly simpler edit without using extra list:

local function GetNeighbors()
	
	local neighbors = {}
	
	for i, center in pairs(openList) do
		for i, node in pairs(Nodes) do
			if node.Position.X / 8 == center.Position.X / 8 and node.Position.Z / 8 + 1 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 == center.Position.X / 8 and node.Position.Z / 8 - 1 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 + 1 == center.Position.X / 8 and node.Position.Z / 8 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			elseif node.Position.X / 8 - 1 == center.Position.X / 8 and node.Position.Z / 8 == center.Position.Z / 8 then
				table.insert(neighbors, node)
			end
		end
		
		table.insert(closedList, center)
		
	end
	
	table.remove(openList, 1)
	
	return neighbors
	
end

And here is the result: