[Resource] A* Implementation (Pathfinding)

[Port]

Yeah, I am realizing now that I need some sort of dynamic pathfinding system for SCP-096.

What do you mean by "dynamic"?

[Ad Bot]

[BluetoothBoy]

As in the player's location (AI's destination) is constantly shifting. Unless the player is stupid and stays in one spot, waiting to die.

[Port]

As in the player's location (AI's destination) is constantly shifting. Unless the player is stupid and stays in one spot, waiting to die.

Albeit it isn't optimal, there's no problem with recalculating the path every time the player moves and the node closest to them changes.
In fact, my zombie mod does that, and runs just fine even with 30+ zombies at once.

[BluetoothBoy]

Albeit it isn't optimal, there's no problem with recalculating the path every time the player moves and the node closest to them changes.
In fact, my zombie mod does that, and runs just fine even with 30+ zombies at once.

Cool. Do you by chance have some code I could insert into my existing AI code? I could probably figure it out after enough time, trial and error, but I don't want this to take too long. Don't worry, I'll credit you. Don't bother taking the time to add the recalculation stuff if you do have some code you'll let me use, I can do that myself.

I'll feel like an idiot if it turns out to be the code in the OP... :/

[Greek2me]

Bumping to post some basic cliff detection code.

Code: [Select]

function isCliffBlocking(%nodeA,%nodeB,%maxCliffHeight)
{
if(%maxCliffHeight $= "")
%maxCliffHeight = 5;

%posA = %nodeA.position;
%posB = %nodeB.position;
%typeMask = $TypeMasks::fxBrickObjectType & $TypeMasks::EnvironmentObjectType;

for(%e = 0.1; %e < 1; %e += 0.1)
{
%posC = vectorAdd(%posA,vectorScale(vectorNormalize(vectorSub(%posB,%posA)),vectorDist(%posA,%posB) * %e));
%posD = vectorSub(%posC,"0 0" SPC %maxCliffHeight);
%hit = containerRayCast(%posC,%posD,%typeMask,%obj);
if(!isObject(firstWord(%hit)))
{
return true;
}
}

return false;
}

[Port]

What is that actually supposed to do?
Wouldn't checking if a cliff is blocking be as simple as:

• checking if ray between %posA + "0 0" SPC maxStepHeight and %posB + "0 0" SPC maxStepHeight is intersected
• calculating angle from %posB - %posA and making sure it's below runSurfaceAngle

(replacing vector operations with appropriate vector..() methods and using player datablock fields)

[Greek2me]

It checks whether there is a dropoff in the way so that they don't fall off of cliffs.

[Lugnut]

does A* only work with 2d coordinates, or does it work with a z value as well?

like, if i had a wall with an overhang, and i wanted to plot a path to the wall, up the wall, under the overhang, around on top of the overhang, then down the other side, would that work, or would it die after trying to climb the wall?

[Port]

does A* only work with 2d coordinates, or does it work with a z value as well?

like, if i had a wall with an overhang, and i wanted to plot a path to the wall, up the wall, under the overhang, around on top of the overhang, then down the other side, would that work, or would it die after trying to climb the wall?

The only thing it uses positions for is calculating path costs, whose heuristic you can change around in your version if needed (default is vectorDist). The main code doesn't even care whether or not there's a position; it only uses neighbor attributes.

[Lugnut]

so it should literally just work if there's a way up? oh, i guess that makes sense.

if you consider the idea that, to the algorithm, it's essentially just walking along a flat plane to get from a to b, it just happens to be that that "plane" is actually going up a wall.


basically, i was looking at the old creeper gamemode and wondering if it could be improved somehow through this algorithm

[Greek2me]

Is there any news on that update you were talking about?

[Port]

Is there any news on that update you were talking about?

I haven't tested it, but if you feel like it, go ahead:
https://hostr.co/6DnGIUu71tVV

[Greek2me]

I haven't tested it, but if you feel like it, go ahead:
https://hostr.co/6DnGIUu71tVV

Thank you, that looks so much more useable.

[Greek2me]

The path is not coming out in the correct order.

Edit: Found the problem after way too much troubleshooting. Your prependToList function is the same as appendToList.

[Alphadin]

Never payed much mind to this, but that video intrigued me. Does it still use nodes or was that removed? Is there a list of extra functions and extra bits and bobs?