I am currently in the process of programming a monster/enemy that has to be able to traverse through a maze-like facility in order to find you. The pathfinder is working well, except when, well, it doesn’t.
My current issue is the fact that sometimes the player might stand in a specific spot, like on a table or chair, and this completely throws off the pathfinder and it cannot find a path that will lead to the player.
With the old pathfinder this is fine because it would just return the closest path to the player, regardless of any obstacles.
With the new pathfinder, however, it will not return anything at all if the path is impossible. This makes it difficult to order the monster to go through the map because it has no path to work with, compared to the old pathfinder where it would at least have a lead that it can follow to find you.
The main question here is: Is it possible to get the closest path to a specified object, even if a normal path isn’t possible?
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 concept of ‘rooms’ and use that to make a very quick pathfinder. Without my further blabbering, here you are:
-- 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
A couple things to note. Some functions are blank because they are specific to your game. If you need help writing them, it might be appropriate to make another topic for them. Also, I haven’t tested this code. I’ve written a couple pathfinders though, so it should be pretty close. Lastly, some features could be added to make it more performant if required. #1 on that list would probably be a priority queue instead of an array. There are many free versions on GitHub. Precomputing which rooms are connected vs disjoint (like separate buildings) would also greatly speed up the process so not every room needs to be searched to find out there isn’t a connection. You shouldn’t need more optimization than that unless you are running hundreds of NPC or have a very big place.