Author Topic: [Resource] A* Implementation (Pathfinding) (Read 20620 times)

Xalos · September 09, 2013, 04:33:52 AM

I want to use this for my Murder Mystery server, but there are some problems. For instance, one map has a large number of portal pairs that players can travel through.

A bot (black dot) chasing its target (yellow dot) would take a path that avoids the portals, because of the length between the nodes at their mouths (15 units). Thus, the bot takes this path (17 units).

However, the true shortest path is to go through the portals, for a final length of 11 units.

Does this script have any support for zero-length paths, AKA portals?

Ad Bot · Advertisement

Port · September 09, 2013, 06:11:12 AM

The new version will include an optional parameter for which heuristic function to use.
You could specify your own and return 0 if the two node pairs it gives you are for portals.

boodals 2 · September 09, 2013, 12:53:19 PM

Couldn't you just make it prefer paths with less nodes?

Port · September 09, 2013, 12:54:28 PM

Quote from: boodals 2 on September 09, 2013, 12:53:19 PM

Couldn't you just make it prefer paths with less nodes?

You could do the same thing using an alternate heuristic function.

Furling� · September 09, 2013, 02:51:32 PM

I use tool node editor, and set it up. how I make bot run follow to the nodes?

Greek2me · September 09, 2013, 07:48:53 PM

Quote from: Port on September 09, 2013, 02:00:23 AM

Nice work. Great job on the function documentation.
Here's what I mainly use - it's a bit more complex as it supports hint nodes through a typemask for node flags, one-way node connections and fast engine-powered near-node searching.

Thanks, the documentation is designed for my TorqueDoc script. I'll probably polish it up and release it later.

I completely forgot about radius searches - I might use that. The rest of the stuff is too complex for what I need. I'm trying to make this as easy as possible for the users, so they will simply plant a special brick at every corner or whatever.

I've run into some problems with the hole bot pathing script.

https://bitbucket.org/Greek2me/slayer/commits/a2ecfcd64222b9ae1b8cd008a29047d668588a5f

It seems like the path had not yet been fully created, so the bots just stopped. I worked around it using callbacks. (lines 1-20)

Bots often could not find the next node until I changed line 97 from %this.getPosition(); to %this.getHackPosition();

Also, I was wondering when it is safe to delete the paths.

Port · September 10, 2013, 01:58:56 AM

Quote from: Greek2me on September 09, 2013, 07:48:53 PM

I completely forgot about radius searches - I might use that.

Well let me say it like this: I made the AI in my zombie mod ~70%+ faster across the board by using radius searches rather than looping over every node (I had about 488 nodes in the map I was using). Before, with 20 zombies there'd be extreme framedrops over and over for the host - afterwards, everything was smooth even with 40 zombies.

Quote from: Greek2me on September 09, 2013, 07:48:53 PM

I've run into some problems with the hole bot pathing script.

https://bitbucket.org/Greek2me/slayer/commits/a2ecfcd64222b9ae1b8cd008a29047d668588a5f

It seems like the path had not yet been fully created, so the bots just stopped. I worked around it using callbacks. (lines 1-20)

Yeah, I'm pretty sure the hole bot pathing script was made for the old version where findPath was blocking and returned the result immediately.

Quote from: Greek2me on September 09, 2013, 07:48:53 PM

Bots often could not find the next node until I changed line 97 from %this.getPosition(); to %this.getHackPosition();

The rays for RPF probably ended up clipping into the ground.

Quote from: Greek2me on September 09, 2013, 07:48:53 PM

Also, I was wondering when it is safe to delete the paths.

Whenever you don't need it anymore - nothing relies on them and the "processing tick" will immediately stop if you delete it, so feel free to delete incomplete paths as well.
EDIT: The new version will include ::ref and ::unref methods which will automatically delete the path when nothing is using it anymore.

Greek2me · September 10, 2013, 04:09:49 PM

Quote from: Port on September 10, 2013, 01:58:56 AM

Yeah, I'm pretty sure the hole bot pathing script was made for the old version where findPath was blocking and returned the result immediately.

I assumed as much. I tried changing it to use findPathBlocking, but the game stopped responding. I didn't have time to debug it.

Quote

Well let me say it like this: I made the AI in my zombie mod ~70%+ faster across the board by using radius searches rather than looping over every node (I had about 488 nodes in the map I was using). Before, with 20 zombies there'd be extreme framedrops over and over for the host - afterwards, everything was smooth even with 40 zombies.

Since my nodes are bricks, that might end up being less efficient for me. You could theoretically have thousands of bricks within the radius.

Furling� · September 11, 2013, 08:19:07 AM

what about automatically Pathfinding?

Aide33 · September 12, 2013, 02:21:21 PM

Quote from: Furling� on September 11, 2013, 08:19:07 AM

what about automatically Pathfinding?

Like without nodes?

Furling� · September 14, 2013, 04:08:17 AM

Quote from: Aide33 on September 12, 2013, 02:21:21 PM

Like without nodes?

something like that, Why not.

BluetoothBoy · September 14, 2013, 07:29:24 AM

Quote from: Furling� on September 14, 2013, 04:08:17 AM

something like that, Why not.

That would involve object detection - I guess, provided that the bot knew it's end coords, it could do a raycast for objects in front of it, scheduled every second or so. When it does encounter an object, it performs a sweeping raycast finding the nearest possible "exit"; distance greater than the hypotenuse of the triangle it is searching from (i.e. player is looking at something, distance from player to object is leg of triangle; distance from player to object as the angle of the raycast changes is the hypotenuse). It would turn to this direction, pass the other object, and continue moving towards its destination.

This is the most basic of basic pathfinding methods, but it should work for simple structures. I'm sure there's another non-node type that could be implemented with enough time and effort, but not by me. It'd be great if it could map out its route before hand, using the above for unexpected object encounters (i.e. a player).

Port · September 14, 2013, 08:01:53 AM

Quote from: BluetoothBoy on September 14, 2013, 07:29:24 AM

That would involve object detection - I guess, provided that the bot knew it's end coords, it could do a raycast for objects in front of it, scheduled every second or so. When it does encounter an object, it performs a sweeping raycast finding the nearest possible "exit"; distance greater than the hypotenuse of the triangle it is searching from (i.e. player is looking at something, distance from player to object is leg of triangle; distance from player to object as the angle of the raycast changes is the hypotenuse). It would turn to this direction, pass the other object, and continue moving towards its destination.

This is the most basic of basic pathfinding methods, but it should work for simple structures. I'm sure there's another non-node type that could be implemented with enough time and effort, but not by me. It'd be great if it could map out its route before hand, using the above for unexpected object encounters (i.e. a player).

I've actually been working on a navigation mesh (far more complicated than simple nodegraphs) generator for Blockland. It works perfectly and all, but I'm stuck on generating a minimum set of rectangles from the result, which is needed before it'd actually be practical to use it.

Aide33 · September 14, 2013, 10:53:57 AM

Quote from: Port on September 14, 2013, 08:01:53 AM

I've actually been working on a navigation mesh (far more complicated than simple nodegraphs) generator for Blockland. It works perfectly and all, but I'm stuck on generating a minimum set of rectangles from the result, which is needed before it'd actually be practical to use it.

Ooo do want

BluetoothBoy · September 14, 2013, 12:10:56 PM

Yeah, I am realizing now that I need some sort of dynamic pathfinding system for SCP-096. Since he doesn't immediately get up and attack the player, it needs some way to find the player through the maze of hallways, even once the player has tried to lose it. Does anyone know how it's done in the actual SCP game? Also, since Shy Guy can be stopped by "no known object", does that mean he should be able to fake kill doors to get to the player?

Last question not really pathfinding related, I'll probably just let The Brighter Dark decide that one. If anyone could answer the first one, that would be excellent.