I have created a game concept that uses A* pathfinding. For those familiar with pathfinding, you may have come into contact with a simulator such as this one. In this simulator, there is an option called “don’t cross corners,” which makes sure the path doesn’t touch wall corners so the character doesn’t get stuck.
Simply put, I need to implement this same effect into my own game, but I’m not sure how to do it. I have skimmed search results in the Roblox forum, as well as the internet in general, but nothing seemed to give details on how to tackle the situation.
There is one key feature about my node grid that I must mention: unlike the simulations and tutorials I have seen, my map does not have nodes defined as obstacles. Instead, where there is a cliff, the nodes on either side are not defined as neighbors.
Below is the script I use to generate nodes at the start of the game. I also have a separate thread that has my pathfinding code, if needed.
--darthbl0xx's Node Generator
--This script generates pathfinding nodes based on the composition of the map
local ServerStorage = game:GetService("ServerStorage")
local GameFolder = ServerStorage:WaitForChild("Game")
local nodesFolder = GameFolder:WaitForChild("Nodes")
--Create a table to store all the nodes (nodes in this list will be indexed by their x and y positioning in the form of a string
local allNodes = {}
--local platformsFolder = workspace.Platforms
local mapExtents = workspace.Platforms.Baseplate.Size
local mapLength, mapWidth = mapExtents.X, mapExtents.Z
--print(mapLength, mapWidth) --DEBUG
--These are the base directional vectors we can take from a single node.
local DIRECTIONS = {
Vector2.new(0, 1),
Vector2.new(1, 1),
Vector2.new(1, 0),
Vector2.new(1, -1),
Vector2.new(0, -1),
Vector2.new(-1, -1),
Vector2.new(-1, 0),
Vector2.new(-1, 1)
}
local BLOCK_SIZE = 4
local OFFSET = BLOCK_SIZE / 2
local function snapTo(number, step)
return number - (number % step)
end
local function placeNode(location)
-- print("Placing a node...") --DEBUG
local nodePart = Instance.new("Vector3Value")
nodePart.Name = "Node"
nodePart.Value = location
nodePart.Parent = nodesFolder
allNodes[tostring(nodePart.Value.X .. " " .. nodePart.Value.Z)] = nodePart
return nodePart
end
local function displayPart(location) --DEBUG
-- print("Displaying a node...") --DEBUG
local testPart = Instance.new("Part")
testPart.Size = Vector3.new(1, 1, 1)
testPart.Material = Enum.Material.Neon
testPart.Name = "Node"
testPart.Position = location
testPart.Anchored = true
testPart.CanCollide = false
testPart.Transparency = 0.5
testPart.Parent = workspace
return testPart
end
local function createEdge(pointA, pointB) --DEBUG
local part1 = Instance.new("Part")
part1.Transparency = 1
part1.CanCollide = false
part1.Anchored = true
part1.Position = pointA
local attachment1 = Instance.new("Attachment")
attachment1.Parent = part1
local part2 = Instance.new("Part")
part2.Transparency = 1
part2.CanCollide = false
part2.Anchored = true
part2.Position = pointB
local attachment2 = Instance.new("Attachment")
attachment2.Parent = part2
local beam = Instance.new("Beam")
-- beam.Color = Color3.fromRGB(0, 255, 0)
beam.FaceCamera = true
beam.Parent = part1
beam.Attachment0 = attachment1
beam.Attachment1 = attachment2
part1.Parent = workspace
part2.Parent = workspace
-- wait(0)
end
local function visualizeNodes() --DEBUG
local nodes = nodesFolder:GetChildren()
for node = 1, #nodes do
local visual = Instance.new("Part")
visual.Size = Vector3.new(1, 1, 1)
visual.Material = Enum.Material.Neon
visual.Name = "Node"
visual.Position = nodes[node].Value
visual.Anchored = true
visual.CanCollide = false
visual.Transparency = 0.8
visual.Parent = workspace
end
end
local function toWorld(number1, number2)
return ((number1 - (number2 / 2)) * BLOCK_SIZE) - OFFSET
end
--Iterate through each chunk of the map and place a node on its surface
--[[
NOTE: Nodes are also generated on inaccessible cliffs. However, these nodes will only
be linked to each other, and will essentially not be used.
]]--
--[[
NOTE: The generator always assumes that the map is centered at (0, 0, 0).
]]--
local xBlocks = snapTo(mapLength / BLOCK_SIZE, 1)
local zBlocks = snapTo(mapWidth / BLOCK_SIZE, 1)
--print(xBlocks, zBlocks) --DEBUG
for x = 1, xBlocks do
for z = 1, zBlocks do
local worldVector = Vector3.new(toWorld(x, xBlocks), 50, toWorld(z, zBlocks))
-- print(worldVector) --DEBUG
local ray = Ray.new(worldVector, (Vector3.new(worldVector.X, -50, worldVector.Z) - worldVector).Unit * 50)
-- displayPart(ray.Origin) --DEBUG
local raycastResult = workspace:Raycast(ray.Origin, ray.Direction, RaycastParams.new())
if raycastResult then
-- print("Object/terrain hit:", raycastResult.Instance:GetFullName()) --DEBUG
-- print("Hit position:", raycastResult.Position) --DEBUG
-- print("Surface normal at the point of intersection:", raycastResult.Normal) --DEBUG
-- displayPart(raycastResult.Position) --DEBUG
local node = placeNode(raycastResult.Position)
else
-- print("Nothing was hit!")
end
-- local y = raycastResult.Position.Y
-- print(x, y, z) --DEBUG
end
-- wait()
end
--visualizeNodes() --DEBUG
--Iterate through all the nodes that have been made and create "neighbor" values inside of them
for _, node in pairs(allNodes) do
-- print(node.Name)
-- print(node.Value) --DEBUG
for _, direction in ipairs(DIRECTIONS) do
-- print(direction.X, direction.Y) --DEBUG
local stringPosition = tostring(node.Value.X - (direction.X * BLOCK_SIZE) .. " " .. node.Value.Z - (direction.Y * BLOCK_SIZE))
-- print(stringPosition) --DEBUG
local neighbor = allNodes[stringPosition]
if neighbor then
-- print(allNodes[stringPosition]) --DEBUG
-- print(node.Value.Y, neighbor.Value.Y) --DEBUG
local yDifference = math.abs(neighbor.Value.Y - node.Value.Y)
-- print(yDifference) --DEBUG
if yDifference <= 2.01 then
-- print("True neighbor") --DEBUG
-- print("The nodes are " .. (node.Value - neighbor.Value).magnitude .. " studs away from each other") --DEBUG
-- createEdge(node.Value, neighbor.Value) --DEBUG
local neighborValue = Instance.new("ObjectValue")
neighborValue.Name = "NeighborNode"
neighborValue.Value = neighbor
neighborValue.Parent = node
end
end
end
-- wait(1/1000000) --DEBUG (This is typically used with the 'createEdge' function so as to prevent exceeding the execution time limit)
end
My final though on this topic: I have a possible solution that iterates through all the nodes once they are generated, looks for a corner, and snips the connection between the two nodes that would cause the path to cross it. The only reason I haven’t tried this yet is because it would be very code redundant (having to look for a specific organization of nodes in four different orientations), and I despise code redundancy with a burning passion.
