[PLUGIN] AGS Pathfinder (EXPERIMENTAL) 0.1.0

Started by eri0o, Wed 21/08/2019 02:51:17

Previous topic - Next topic

eri0o

Hey guys,

I need help with people to test this and give suggestions, even for naming things.

AGS Pathfinder Plugin version 0.1.0

Get the plugin: agspathfinder.dll, libagspathfinder.solibagspathfinder.dylib 
GitHub Repo | Demo Windows | Demo Linux



This plugin has copy of the actual pathfinder used by Adventure Game Studio, and exposes an interface to interact directly with it.

It's in experimental state because I believe that once the API for it is figured out, it's facilities would be provided by AGS Engine itself and then this Plugin would not make sense anymore.

AGS Pathfinder usage

Pathfinding is provided in three steps.

1. Set the map, Pathfinder will generate the nodes. Don't do this every frame.

2. Get the path as a vector by passing an origin and a destination.
   If your node map is not too gigantic, this should be very fast.
   If start and end of the vector doesn't match your origin and destination, no
   path was found. Ideally the vector returned should be empty.

3. Consume the returned vector and do something with it.

Code: ags

// 1 Pass sprite 1 to be used as map
AgsPathfinder.SetGridFromSprite(1);

// 2 Calculates the path and returns a vector containing all the nodes
PathNodeArray* pathNodeArr = AgsPathfinder.GetPathFromTo(origin_X, origin_Y, destination_X, destination_Y);

// 3 Consume your path node by node
while(!pathNodeArr.Empty()){
  PathNode* pathNode = pathNodeArr.Pop();
  // do something with pathNode.X and pathNode.Y
}


AGS Pathfinder Script API


void AgsPathfinder.SetGridFromSprite(int sprite)

Pass a sprite to be used as the walkable map. Real black (000000) identifies walls.

PathNodeArray* GetPathFromTo(int origin_x, int origin_y, int destination_x, int destination_y)

Get a PathNodeArray containing each Node of the path for the provided origin and destination.

eri0o

I reflected and it's missing some way to tell the grid map is not initialized yet and some way to clear it. Also need to serialize the map and load from the serialized data on game restore.

Crimson Wizard

#2
I've already mentioned before, my belief is that it may be relatively easy to export in the engine. The only problem is to decide how to return the path: use existing AGS script functionality (plain array) with some workaround to indicate its length, or create completely new container.

The initial suggestion was to, for starters, implement this as a dynamic array of Points (struct Point was introduced in 3.5.0), and have last element = null to indicate it's end.

This would look like:
Code: ags

Point path[] = Game.FindPath(sprite_num, sx, sy, dx, dy);
if (path == null)
     return; // no path found
for (int i = 0; path[i] != null; i++)
{
}


In the above, the problem is that you cannot pass room's walkable mask as a sprite number, because it's not a sprite. So, unless you want user to copy walkable areas to sprite first, the workaround could be to also add another function which would exclusively find paths in the room using currently enabled areas, like
Code: ags

Point path[] = Room.FindPath(sx, sy, dx, dy);

eri0o

#3
Whoa, that may actually work too. The Room may reuse the current Navigation instance nav, the Game would need a new instance for the an arbitrary sprite. My use case was actually an arbitrary script, since I wanted to generate my walkables using agsfastwfc. Maybe we could have too a GetLastPathLength() . A bit ugly but works.   ;-D

Ah, it would be interesting if it could in some way know that the sprite has been passed before, because then it wouldn't need to regenerate the Navigation.map nodes, which appears to be slower than actually calculating the path.

Crimson Wizard

Quote from: eri0o on Thu 22/08/2019 23:11:47
Ah, it would be interesting if it could in some way know that the sprite has been passed before, because then it wouldn't need to regenerate the Navigation.map nodes, which appears to be slower than actually calculating the path.

Hmm yes, that's another issue. Perhaps generic API could be expanded to have a pathfinder grid instance. Of course that would require extra objects, so one have to be careful when designing that.

The room variant does not need that because it has internal maps already.

eri0o

#5
Uhm, I mean, just keep the same api as you said, but if the number is the same as previous, do not regenerate the map. If someone loads a save, the sprite will be passed and the clean map will then be initialized. If someone needs to pass the same map twice, since the sprite has the same number as previous nothing happens. We can add a note that passing -1 as sprite number, reloads the previous sprite. This way we just need to serialize an int (the sprite number) instead of the full map. This skips the need for an extra object.

Crimson Wizard

#6
Quote from: eri0o on Thu 22/08/2019 23:27:53
Uhm, I mean, just keep the same api as you said, but if the number is the same as previous, do not regenerate the map. If someone loads a save, the sprite will be passed and the clean map will then be initialized. If someone needs to pass the same map twice, since the sprite has the same number as previous nothing happens. We can add a note that passing -1 as sprite number, reloads the previous sprite. This way we just need to serialize an int (the sprite number) instead of the full map. This skips the need for an extra object.

Yeah, that's an option, but imho not the optimal one if, say, you have several maps at once.

In contemporary engines you usually have NavMesh objects per each map, maybe ags could provide something similar.

eri0o

#7
Ok, I gave it some thought, and Navigation (the class in router_finder_jps.inl) has map and mapNodes. Somehow I think navmesh is something more similar to a Navigation alternate class that has these Nodes as a first class element, where a node could be connected to N nodes, and you are solving this path problem for a group of nodes that don't necessarily map to... A map, a thing with X,Y positions. (Example, like the the levels on super Mario world connect as nodes.)

I feel for X,Y positions the concept of navmesh could be abstracted to a navmap. The difference is the navmap is this object that the Nodes are actually mapNodes, and then derived from an input map, similar to the walkable bitmap, but a sprite, or a 2D matrix, or similar.

So, in examples, something like this.

Code: ags

// Initializes from an int sprite 
Navmap* myMap = Navmap.CreateFromSprite(2);

// find path from source x,y to destination x,y
Point path[] = myMap.FindPath(20, 64, 100, 300);
if (path == null)
     return; // no path found
for (int i = 0; path[i] != null; i++)
{
}


The above would still only require storing the sprite number instead of the full map. Also it would be reasonable provide a myMap.Update() that regenerates the map for the original sprite identifier in case it gets edited by drawing on it's surface or something.

Then on Navmesh, in my mind, it's a bit more complex...



Code: ags

Navmesh* myMesh = new Navmesh;

myMesh.AddVertex(/* id */ 1);
myMesh.AddVertex(/* id */ 2);
myMesh.AddEdge(/*p1 id */ 1, /* p2 id*/ 2, /* "effort" */ 5);
myMesh.AddVertex(3);
myMesh.AddEdge(1, 3, 25);
myMesh.AddVertex(4);
myMesh.AddEdge(3, 4, 1);
myMesh.AddEdge(2, 4, 1);

int mesh_path[] = myMesh.FindPath(1,4);
//mesh path will be an array containing [1,2,4,0]


Don't know if my notation makes sense... But when I read on, mesh is just squares on 2D games, so I think you are right. Just giving some thoughts on what I imagined. Note: I have no experience with contemporary engines.

SMF spam blocked by CleanTalk