[Resource] A* Implementation (Pathfinding)

[Port]

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.

.. haha, yeah, as I said, I really haven't tested that version and I'm not even sure how finished it is.

[Ad Bot]

[0xBRIANSMITH]

What changes did you make?

[Greek2me]

.. haha, yeah, as I said, I really haven't tested that version and I'm not even sure how finished it is.

I think that was the only thing wrong. I made two changes:

https://bitbucket.org/Greek2me/slayer/diff/Support/Support_Pathing/Support_Pathing.cs?diff2=0f3c65f29fc6&at=dev
https://bitbucket.org/Greek2me/slayer/diff/Support/Support_Pathing/finders/AStarFinder.cs?diff2=b8b24348d3f6&at=dev


Edit: I'm running into this problem now.

Code: [Select]

base/Slayer/Support/Support_Pathing/BaseFinder.cs (10): Unknown command schedule.
  Object (49178) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
base/Slayer/Support/Support_Pathing/finders/AStarFinder.cs (9): Unknown command callHeuristic.
  Object (49178) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
base/Slayer/Support/Support_Pathing/finders/AStarFinder.cs (11): Unknown command schedule.
  Object (49178) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject

Code: [Select]

base/server/scripts/game.cs (1380): Unknown command getType.
  Object (49178) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
base/server/scripts/game.cs (1380): Unknown command getType.
  Object (49178) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
It seems like the object hasn't been fully created by the time ::onAdd is called. All of the needed files have been executed.

[0xBRIANSMITH]

I mean what was the change between the one in the OP and the one port just posted.

[Greek2me]

I mean what was the change between the one in the OP and the one port just posted.

I posted that for Port's benefit.

The main changes are that the API allows you to use your own algorithm and heuristic.

[Greek2me]

Some more info about that bug I'm seeing...

The path object is created, but it seems like it isn't inheriting from the ScriptObject class.

base/Slayer/Support/Support_Pathing/BaseFinder.cs (10): Unknown command schedule.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
base/Slayer/Support/Support_Pathing/finders/AStarFinder.cs (9): Unknown command callHeuristic.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
base/Slayer/Support/Support_Pathing/finders/AStarFinder.cs (11): Unknown command schedule.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
Slayer (Server): AiPlayer::goToObjective: Using path 25531
==>25531.dump();
<input> (0): Unknown command dump.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
Window reactivating...
Window reactivating...
==>slayer.pathhandler.paths.list objects();
   25531: ScriptObject
==>25531.dump();
<input> (0): Unknown command dump.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
Posting to rtb server
==>echo(isObject(25531));
1
==>25531.dump();
<input> (0): Unknown command dump.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
==>25531.test = "blah";
==>echo(25531.test);
blah
==>25531.setName("testing");
<input> (0): Unknown command setName.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject
Window reactivating...
Window reactivating...
==>echo(25531.getClassName());
<input> (0): Unknown command getClassName.
  Object (25531) AStarFinder -> BaseFinder -> ScriptObject -> SimObject -> SimObject

After removing the class = %finder; line from the script, the object was created properly.

Slayer (Server): Slayer_NodeTriggerData::onEnterTrigger: 24659^24616^26732^20535
Slayer (Server): AiPlayer::goToObjective: Using path 26772
==>26772.dump();
Member Fields:
  superClass = "BaseFinder"
Tagged Fields:
  A = "24609"
  B = "24614"
  Bot = "26732"
  callBack = "Slayer_onBotPathFound"
  done = "0"
  heuristic = "euclideanPathCost"
Methods:
  addScheduledEvent() -
  call() -
  callHeuristic() -
  cancelEvents() -
  clearEvents() -
  clearNTObjectName() -
  delete() - obj.delete()
  dump() - obj.dump()
  dumpEvents() -
  end() -
  getClassName() - obj.getClassName()
  getGroup() - obj.getGroup()
  getGroupID() -
  getId() - obj.getId()
  getName() - obj.getName()
  getTaggedField() - obj.getTaggedFieldCount(int idx)
  getType() - obj.getType()
  onAdd() -
  onCameraEnterOrbit() -
  onCameraLeaveOrbit() -
  processInputEvent() -
  save() - obj.save(fileName, <selectedOnly>)
  schedule() - object.schedule(time, command, <arg1...argN>);
  scheduleNoQuota() - object.schedule(time, command, <arg1...argN>);
  serializeEvent() -
  serializeEventToString() -
  SetEventEnabled() -
  setName() - obj.setName(newName)
  setNTObjectName() -
  ToggleEventEnabled() -

Obviously that's not a solution though since I need the A* methods.

edit: Full console log: http://www.filedropper.com/console_1


edit2: Of course, none of that makes sense because it's definitely possible to define both the class and the superClass on a ScriptObject:

Code: [Select]

%mini = new scriptObject()
{
class = Slayer_MinigameSO;
superClass = MinigameSO;
//snipThis works fine. Why doesn't Port's code seem to?

[Port]

I currently have no idea why that's happening, sorry. In other news, I've been working on a nodeless Jump Point Search implementation. 2D works just fine in my tests; I'm just trying to adapt it to allow variance in Z for neighbors.

[Greek2me]

I currently have no idea why that's happening, sorry. In other news, I've been working on a nodeless Jump Point Search implementation. 2D works just fine in my tests; I'm just trying to adapt it to allow variance in Z for neighbors.

Hm :/ I'll see if I can figure it out.

That sounds interesting.. How does it compare to A* performance-wise? Fairly well apparently. This is a nice demonstration: http://qiao.github.io/PathFinding.js/visual/

I wonder how well a nodeless system would work with bots. I think that I would need to create a trigger, and when the bot reaches it, move the trigger to the next point and have the bot walk in that direction.

[Port]

How does it compare to A* performance-wise?

It can find a full path from one side of half of the ZAPT "Dam" map to the other in ~1 second (obviously, without /any/ nodes).
This is without my HeapQueue implementation and the following timing:

%this.schedule = %this.schedule(getRealTime() - %tickStart, run);

[Port]

I've written a heap queue implementation which greatly speeds up and simplifies most pathfinding algorithms.

https://gist.github.com/portify/7831259

Here's an example of simplifying basic A* with it:

function AStar(%a, %b) {
   %open = HeapQueue(%a);
 
   while (%open.size) {
      %node = %open.pop();
      %closed[%node] = 1;
 
      if (%node.getID() == %b.getID()) {
         while (%node !$= "") {
            %path = %node @ (%path $= "" ? "" : " ") @ %path;
            %node = %parent[%node];
         }
 
         return %path;
      }
 
      for (%i = 0; %i < %node.links; %i++) {
         %link = %node.link[%i];
 
         if (!%closed[%link]) {
            %parent[%link] = %node;
 
            if (!%open.contains(%link)) {
               %open.push(%link, vectorDist(%node.position, %link.position));
            }
         }
      }
   }
 
   return "";
}

[Greek2me]

Bump. Any news on the JPS?

In the meantime, I've implemented the heap queue and have begun writing the jump-point search myself (along with a grid system):

https://bitbucket.org/Greek2me/slayer/src/96d4481dd04b7f4e5ebf3bc19ca0a7fa2047b318/Support/Support_Pathing/?at=dev