How can I get the pathfinding algorithm to ignore certain blocks?

[marfit]

I have an NPC that is capable of opening doors. The only problem is, most of the time the door is shut, therefore blocking a path to the player. How would I get the pathfinding algorithm to ignore the doors?

[deedubbleyew]

Maybe split the path into smaller paths, with the NPC halting just before the doors, opening them, then continuing?

[RedDuck765 (RedDuck)]

You could maybe create a table with all of the doors in it and every time your pathfindig system runs, loop through the table to check that you aren’t counting a door block?

I’m not sure what algorithm you’re using or how you’ve implemented it so this might not work at all.

[IdiomicLanguage]

I’ll give my usual pathfinding response: write your own pathfinder. It is rather trivial once you’ve built one to not include some parts or add a check to see if a condition is met and if not factor in the time to make that condition true. (Possibly requiring a trip to go grab a key, waiting for another NPC with the key, or taking a moment to open / hack the door.)

[marfit]

Man, that seems like a pretty daunting task. I remember a post about someone doing it and some weird things came up like “A*”. Do you have any potential resources I could use?

[RedDuck765 (RedDuck)]

A* is a type of path finding algorithm. There are many tutorials for implementing this in other languages that I’m sure you could easily convert to Roblox. I’m also fairly sure that there is an A* tutorial on the wiki.

For pathfinding algorithms, Wikipedia is often surprisingly useful. Most of the time it provides pseudo code that can be used to make a robust system.

AStar-Algorithm.pdf

(This is some fairly simple pseudo code I found on A*)

Experiment and see what suits you best. A* is just one of a few pathfinding algorithms. See which one works best for you.

[marfit]

What kind are there that can be implemented in roblox other than A*? I’m kind of looking for the best performance.

[SamsonXVI (Samson)]

Maybe you can try making the doors local models instead of being server sided? That way the NPC will completely ignore them but will still be visible to players, and then just fire a remote event that opens the door on the client side.

[marfit]

This’ll be a multiplayer game. I’ve also settled to omit the feature until I can finish my A* pathfinding.

[IdiomicLanguage]

I wrote an example A* implementation that just needs to be filled in with a couple of your game-specific details here:

Finding Closest Path To An Object

Writing your own pathfinder really isn’t too hard. I’ve told people this on other topics, but I don’t think they believe me give up on their features/games. A maze is a perfect place to run a custom pathfinder, because you have special information that the Roblox pathfinder doesn’t know about, specifically the maze structure. I wrote a A* pathfinder for my hexagonal maze geodome and then made the NPC walk in the direction of the player once inside the same cell. You may be able to create the con…

You’ll find the that code has variables with ‘Room’ in their names. This can be simply replaced by ‘Node’ or any other object that is connected to other objects to form any graph. It is intentionally implemented in a way to require the game author to fill in the details for the specific type of object they use.

For simplicity I’ll post the code here:

-- Returns the room that the point is in. This point will often be
-- a character's humanoid root part position.
local function getRoom(point)

end

-- Returns a table. Each key is a room adjacent to the given room,
-- an the value is the cost of walking from one room to another.
-- You can use the straight line distance between room centers
-- for a rough estimate.
local function getAdj(room)

end

-- Returns a number, the minimum cost it will take to get to a point.
-- The more accurate, the faster the algorithm will run. Overestimating
-- will make A* not always find the minimum path. When in doubt, the
-- straight line distance can be used.
local function getDistance(room, gRoom)

end

local function getMin(list)
	local minKey, minVal = next(list)
	for key, val in next, list, minKey do
		if val < minVal then
			minKey = key
			minVal = val
		end
	end
	return minKey
end

local function getPath(start, goal)
	local sRoom = getRoom(start)
	local gRoom = getRoom(goal)

	local fringe = {[sRoom] = getDistance(sRoom, gRoom)}
	local closed = {}
	local ancestry = {}
	local costsToGoal = {[sRoom] = fringe[sRoom]}
	local costsToStart = {[sRoom] = 0}

	local curRoom = sRoom
	while curRoom ~= gRoom do
		closed[curRoom] = fringe[curRoom]
		fringe[curRoom] = nil

		for adjRoom, addCost in next, getAdj(curRoom) do
			local newCost = costsToStart[curRoom] + addCost
			local curCost = costsToStart[adjRoom]
			if closed[adjRoom] then
			elseif curCost then
				if newCost < curCost then
					ancestry[adjRoom] = curRoom
					costsToStart[adjRoom] = newCost
					fringe[adjRoom] = newCost + costsToGoal[adjRoom]
				end
			else
				ancestry[adjRoom] = curRoom
				costsToStart[adjRoom] = newCost
				costsToGoal[adjRoom] = getCost(adjRoom, gRoom)
				fringe[adjRoom] = newCost + costsToGoal[adjRoom]
			end
		end

		curRoom = getMin(fringe)
		if curRoom == nil then
			curRoom = getMin(costsToGoal)
			-- or getMin(closed) to account for travel time to there
			break
		end
	end

	local path = {}
	while curRoom do
		path[#path + 1] = curRoom
		curRoom = ancestry[curRoom]
	end

	-- [1] is closest to the goal, [#path] is close to start
	return path
end

[OPPEYRADY (OPERATOR)]

I have a semi solution if you don’t want to use the above.

Collisions | Documentation - Roblox Creator Hub

Using that and combining it with pathfinding you can make a brick appear “Walkable” for the bot.

You could also use a node for doors to be scripted and do it manually.