A* Pathfinding: Don't Cross Corners

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 function snapTo(number, step)
	return number - (number % step)

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

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

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)

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

local function toWorld(number1, number2)
	return ((number1 - (number2 / 2)) * BLOCK_SIZE) - OFFSET

--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)
--			print("Nothing was hit!")
--		local y = raycastResult.Position.Y
		--		print(x, y, z) --DEBUG
--	wait()
--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
--	wait(1/1000000) --DEBUG (This is typically used with the 'createEdge' function so as to prevent exceeding the execution time limit)

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.

1 Like

You do that when you’re calculating the neighbors for a given node.

Check out the getNeighbors method from the page you linked to (snipped for relevant parts and commented a bit more):

 * Get the neighbors of the given node.
 *     offsets      diagonalOffsets:
 *  +---+---+---+    +---+---+---+
 *  |   | 0 |   |    | 0 |   | 1 |
 *  +---+---+---+    +---+---+---+
 *  | 3 |   | 1 |    |   |   |   |
 *  +---+---+---+    +---+---+---+
 *  |   | 2 |   |    | 3 |   | 2 |
 *  +---+---+---+    +---+---+---+
Grid.prototype.getNeighbors = function(node, diagonalMovement) {
    var x = node.x,
        y = node.y,
        neighbors = [],
        s0 = false, d0 = false,
        s1 = false, d1 = false,
        s2 = false, d2 = false,
        s3 = false, d3 = false,
        nodes = this.nodes;

    // @nicemike40 assign top/bottom/left/right squares walkability first
    // ↑
    if (this.isWalkableAt(x, y - 1)) {
        neighbors.push(nodes[y - 1][x]);
        s0 = true;
    // ... snipped, also assign left, right, down (s1-s3) also

    // @nicemike40 ... then, assign diagonals based on those

    if (diagonalMovement === DiagonalMovement.Never) {
    	// @nicemike40: if no diagonal movement is allowed, stop here
        return neighbors;

    if (diagonalMovement === DiagonalMovement.OnlyWhenNoObstacles) {
    	// @nicemike40: if e.g. top and left are both walkable, only then allow top-left
        d0 = s3 && s0;
        d1 = s0 && s1;
        d2 = s1 && s2;
        d3 = s2 && s3;
    } else if (diagonalMovement === DiagonalMovement.IfAtMostOneObstacle) {
    	// @nicemike40: e.g. allow top-left, only if at least one of top OR left are walkable
        d0 = s3 || s0;
        d1 = s0 || s1;
        d2 = s1 || s2;
        d3 = s2 || s3;

    // ... snipped, neighbors.push for d0-d3

    return neighbors;

Also, as a side note, this is a really good start to an interesting project, but you’re shooting yourself in the foot with how you’re storing and indexing your nodes. It might be helpful to

a) store them in a 2D array where the [x][z] index is implicitly the node’s position on the grid (saving you all the string manipulations)
b) utilize object oriented programming in lua to store your nodes in pure code, rather than creating actual Instances and ObjectValues for things. (another good source here).


  1. Split your DIRECTIONS table into ORTH_DIRECTIONS and DIAG_DIRECTIONS (orthogonal and diagonal directions, respectively.
  2. In your neighbor-finding loop, do the ORTH_DIRECTIONS for a node first, followed by the DIAG_DIRECTIONS.
  3. When figuring out whether to add a diagonal neighbor, also check the previously-calculated orthogonal neighbors. For example, only add the neighbor at (1, -1) if you have a walkable neighbor at both (1, 0) and (0, -1).
  4. Use OOP to save yourself trouble in the future :slight_smile:

If you wanted to be really lazy and cool, you could straight up clone that repo, use roblox-ts to transpile the src/ directory to lua (with probably some minor changes), and just use the same code. That might be a fun project.

I apologize for the late response. I’ve been taking a shot at implementing what you have suggested. It may take some time, but if I can’t seem to figure it out, I’ll just make another forum post, if needed.

Thanks for your help! I’ll mark this thread as solved.