[pamdex]

PathFinder 1.0 MT by Pamdex

Description:
This plugin allows you to calculate a route from point A to B on the San Andreas map.
It uses the built-in MapAndreas 1.2.1 class integration and Djikstra styled algorithm, so you can calculate routes everywhere (not in water).
It also uses separate thread for path calculation.

Dijkstra:

Installation
You must have MapAndreas 1.2.1:
https://sampforum.blast.hk/showthread.php?tid=275492

You have to add PathFinder and MapAndreas to "plugins" line (MapAndreas at the end) in server.cfg. Also you have to put MapAndreas and PathFinder libraries in "plugins" folder.

Callbacks
OnPathCalculated

Code:

OnPathCalculated(routeid, success, Float:nodesX[], Float:nodesY[], Float:nodesZ[], nodesSize)

Parameters:

• routeid <- ID of calculated path
• success <- returns true or false
• nodesX[] <- positions X of nodes
• nodesY[] <- positions Y of nodes
• nodesZ[] <- positions Z of nodes
• nodes_size <- returns amount of nodes

Example usage:

Code:

new text[128];
public OnPathCalculated(routeid, success, Float:nodesX[], Float:nodesY[], Float:nodesZ[], nodesSize)
{
	format(text, sizeof(text), "PATH: route: %d success: %d nodesSize: %d", routeid, success, nodesSize);
	SendClientMessageToAll(-1, text);
	if(success)
	{
		for(new i; i < nodesSize; i++)
	    	{
			CreateDynamicObject(19130, nodesX[i], nodesY[i], nodesZ[i] + 1, 0, 0, 0);
    		}
    		Streamer_Update(0);
	}
	return 1;
}

Warning! When route calculation fails nodesX[], nodesY[], nodesZ[] has only one index with value = -1 (nodes_size is 1).
Warning!

Quote:

The Z return value is accurate to within a few centimetres from the actual ground surface position

If you want to use it to teleport, bots etc. just add 1.0 to Z.

Natives
PathFinder_Init

Code:

PathFinder_Init(mapAndreasAddress, threads = 1);

Parameters:

• mapAndreasAddress <- mem address of CMapAndreas class (see "Using in PAWN")
• threads <- number of threads (more threads = more paths are calculated at the same time)

This function setups the plugin (is required).

PathFinder_FindWay

Code:

PathFinder_FindWay(routeid, Float:startX, Float:startY, Float:endX, Float:endY, Float:zDifference = 0.9, stepSize = 1, stepLimit = -1, maxSteps = 2000);

Parameters:

• routeid <- path ID
• start_x <- start X position
• start_y <- start Y position
• end_x <- end X position
• end_y <- end Y position
• zDifference <- maximum Z difference between nodes (used in path calculating)
• stepSize <- size of step (used in path calculating)
• stepLimit <- steps limit for path calculation. If you set here -1, plugin works in normal mode (without step limit). If path calculating reaches this limit, calculating stops and plugin returns path (max return path size = limit + 1)
• maxSteps <- main step limit. If path calculating reaches this limit, calculating fails.

This function starts path calculation from point A to point B.

PathFinder_MapAndreasLock

Code:

PathFinder_MapAndreasLock();

This function freezes path calculation, so you can use normal MapAndreas natives without problems with threads safety.

Example usage:

Code:

new Float:z;
PathFinder_MapAndreasLock(); //Block PathFinder...

//Do MapAndreas command or smth else like RNPC (with MapAndreas class sharing)
for(new i = 0; i < 1000; i++)
{
	MapAndreas_FindZ_For2DCoord(random(6000) - 3000, random(6000) - 3000, z);
	format(text, sizeof(text), "%d -> %f", i, z);
	SendClientMessageToAll(-1, text);
}
PathFinder_MapAndreasUnlock();

PathFinder_MapAndreasUnlock

Code:

PathFinder_MapAndreasUnlock();

This function unlock path calculation.

PathFinder_SetTickRate

Code:

PathFinder_SetTickRate(rate = 5);

Parameters:

• rate

This function sets tick rate for thread communication. Default value is 10 (10 * 5ms update). Plugin uses tick rate only for outputting calculated ways (not for calculating).

Using in PAWN
New version of PathFinder is based on MapAndreas 1.2.1 class integration code. So initialisation code must looks like that:

Code:

#include <MapAndreas>
#include <PathFinder>
public OnFilterScriptInit()
{
	MapAndreas_Init(MAP_ANDREAS_MODE_FULL);
	PathFinder_Init(MapAndreas_GetAddress());
	return 1;
}

Warning!

Quote:

PathFinder only works with MAP_ANDREAS_MODE_FULL and MAP_ANDREAS_MODE_NOBUFFER !

Video
[ame]http://www.youtube.com/watch?v=VtmWDnRoSSg[/ame]
Description:

• /path_test - normal path calculation from player location to selected location
• /path_test_size - normal path calculation from player location to selected location with stepSize = 2
• /path_test_limit - normal path calculation from player location to selected location with stepLimit = 30
• /path_test_limit_50 - normal path calculation from player location to random location with stepLimit = 10 repeated 50 times

Tested on Intel Core i7-4790K 4.00GHz and 8GB RAM 2400MHz

Download & Source
PathFinder 1.0 MT:
https://bitbucket.org/Pamdex/pathfinder/downloads

Changelog:

• 0.11v <- first release
• 0.12v <- added new "param" to PathFinder_Init and bug-fix
• 0.13v <- added new "param" to PathFinder_FindWay
• 0.14v <- added new function PathFinder_SetTickRate and little bug-fix
• 1.0 RC 2 <- completely rewritten code
• 1.0 MT <- multi-thread version of PathFinder

[Pottus]

Those RNPC bots look pretty crappy, is there anyway to improve their movement?

[pamdex]

You can improve the movement when you "clear" the route e.g. remove unnecessary points.
First video shows the bot without "clear".

[steki.]

Oh, you. Sweet!

[RebeloX]

Very nice

[Pottus]

Tried this out, but my zombies keep getting stuck on roofs, since I need to continually update the path to the player when that happens the path calculation keeps calculating the same position. It's a cool plugin but still really buggy for zombies.

[oOFotherOo]

Very nice.

[Lorenc_]

You're the best. Thanks!

[CoaPsyFactor]

well, this doesn't looks like real path finder, how does it works with SAMP Nodes?

[Pottus]

Ok, some updates on the problem it would seem OnPathCalculated() doesn't even get called in some instances when attempting to calculate a path check out this output.


Update #1
[20:39:49] Iteration: 0 NodeID: 4688619 czyli X = -381.000000 Y = 2219.000000 Z = 41.090000
[20:39:49] Iteration: 1 NodeID: 4694620 czyli X = -380.000000 Y = 2218.000000 Z = 41.090000
[20:39:49] Iteration: 2 NodeID: 4700620 czyli X = -380.000000 Y = 2217.000000 Z = 41.090000
[20:39:49] Iteration: 3 NodeID: 4706620 czyli X = -380.000000 Y = 2216.000000 Z = 41.090000
[20:39:49] Iteration: 4 NodeID: 4712620 czyli X = -380.000000 Y = 2215.000000 Z = 41.090000
[20:39:49] Iteration: 5 NodeID: 4718620 czyli X = -380.000000 Y = 2214.000000 Z = 41.090000
[20:39:49] Iteration: 6 NodeID: 4724620 czyli X = -380.000000 Y = 2213.000000 Z = 41.090000
[20:39:49] X:-380.000000 Y:2216.000000 Z:41.090000 <---- Used Path Node

Update #2
[20:39:50] Iteration: 0 NodeID: 4700619 czyli X = -381.000000 Y = 2217.000000 Z = 41.090000
[20:39:50] Iteration: 1 NodeID: 4706618 czyli X = -382.000000 Y = 2216.000000 Z = 41.279998
[20:39:50] Iteration: 2 NodeID: 4712617 czyli X = -383.000000 Y = 2215.000000 Z = 41.369998
[20:39:50] Iteration: 3 NodeID: 4718616 czyli X = -384.000000 Y = 2214.000000 Z = 41.409999
[20:39:50] Iteration: 4 NodeID: 4724616 czyli X = -384.000000 Y = 2213.000000 Z = 41.419998
[20:39:50] X:-384.000000 Y:2214.000000 Z:41.409999 <---- Used Path Node
----------------------------------------------------- <---- No paths here PathFinder_FindWay() failed
[20:39:50] X:-384.000000 Y:2214.000000 Z:41.409999 <---- Keeps returning the same values since there is no new
[20:39:51] X:-384.000000 Y:2214.000000 Z:41.409999 path updates ("Failed") would be printed if
[20:39:51] X:-384.000000 Y:2214.000000 Z:41.409999 OnPathCalculated() was actually called
[20:39:52] X:-384.000000 Y:2214.000000 Z:41.409999
[20:39:52] X:-384.000000 Y:2214.000000 Z:41.409999
[20:39:52] X:-384.000000 Y:2214.000000 Z:41.409999
[20:39:53] X:-384.000000 Y:2214.000000 Z:41.409999
[20:39:53] X:-384.000000 Y:2214.000000 Z:41.409999

Paths stop being calculated, I'm guessing something is failing inside PathFinder_FindWay(); resulting in OnPathCalculated() not being called.

Edit - Continued doing tests and still the same problem keeps surfacing it's not calculating when using PathFinder_FindWay(); and isn't even calling OnPathCalculated() with a failed success obviously a bug.

Also noticed once nodes stop being calculated properly the plugin then fails completely and won't calculate any paths regardless of the values passed to PathFinder_FindWay();

Some more information:

This part of the code is on a 400 ms timer which keeps the Zombie following the player.

Code:

PathFinder_FindWay(zombie, zx, zy, x, y);
printf("X:%f Y:%f Z:%f", ZombieNextPos[zombie][0],ZombieNextPos[zombie][1],ZombieNextPos[zombie][2]);

Here is OnPathCalculated()

Code:

public OnPathCalculated(routeid,success,nodes[],nodes_size)
{
	if(success)
	{
		new Float:x,Float:y,Float:z;
		for(new i; i < nodes_size; i++)
		{
			PathFinder_GetNodePos(nodes[i],x,y,z);
			printf("Iteration: %d NodeID: %d Position X: %f Y: %f Z: %f",i,nodes[i],x,y,z);
		}

		if(nodes_size > 2) PathFinder_GetNodePos(nodes[2], ZombieNextPos[routeid][0], ZombieNextPos[routeid][1], ZombieNextPos[routeid][2]);
		else if(nodes_size > 1) PathFinder_GetNodePos(nodes[1], ZombieNextPos[routeid][0], ZombieNextPos[routeid][1], ZombieNextPos[routeid][2]);
		else PathFinder_GetNodePos(nodes[0], ZombieNextPos[routeid][0], ZombieNextPos[routeid][1], ZombieNextPos[routeid][2]);
	}
	else
	{
		print("Failed");
		GetPlayerPos(ZombieInfo[routeid][zplayerid], ZombieNextPos[routeid][0], ZombieNextPos[routeid][1], ZombieNextPos[routeid][2]);
	}
}

[cyber_punk]

Why not use the GTA SA path nodes? The code is out on the net for a node reader. Using MapAndreas will not correctly calculate a "path" route..... think about objects less than 1 meter squared, your bots, players whatever you apply your path too can and will walk through those objects. A+ for the effort I like seeing A* instead of Dijkstra method but without the nodes the accuracy of this will not be at the level that it could be.

[Pottus]

Quote:

Originally Posted by cyber_punk Why not use the GTA SA path nodes? The code is out on the net for a node reader. Using MapAndreas will not correctly calculate a "path" route..... think about objects less than 1 meter squared, your bots, players whatever you apply your path too can and will walk through those objects. A+ for the effort I like seeing A* instead of Dijkstra method but without the nodes the accuracy of this will not be at the level that it could be.

I think mostly the purpose is to calculate a path anywhere, I'm guessing the GTA SA path nodes would be limited at any rate this plugin has some serious issues making it unusable at the current time beyond those issues mentioned.

[pamdex]

Ok. I'll see what's wrong in code...

Test this code (without "clear"):

Code:

#include <a_samp>
#include <PathFinder>
#include <rnpc>
new zombie_moved[5];
new zombie_timer;
public OnPathCalculated(routeid,success,nodes[],nodes_size)
{
	if(success)
	{
		new Float:x,Float:y,Float:z,Float:x1,Float:y1,Float:z1;
		RNPC_CreateBuild(routeid,PLAYER_RECORDING_TYPE_ONFOOT);
		//Bot!
		for(new i; i < nodes_size-1; i++)
		{
			PathFinder_GetNodePos(nodes[i],x,y,z);
			PathFinder_GetNodePos(nodes[i+1],x1,y1,z1);
			RNPC_AddMovement(x,y,z+1,x1,y1,z1+1,RNPC_SPEED_RUN); //crappy :D
		}
		RNPC_FinishBuild();
		RNPC_StartBuildPlayback(routeid);
	}
	else
	{
		new text[126];
		format(text,sizeof(text),"Zombie: %d failed!",routeid);
		SendClientMessageToAll(-1,text);
		zombie_moved[routeid] = true;
	}
	return 1;
}
public OnFilterScriptInit()
{
	PathFinder_Init(1.0);
	ConnectRNPC("Zombie1"); //id 0
	ConnectRNPC("Zombie2");
	ConnectRNPC("Zombie3");
	ConnectRNPC("Zombie4");
	ConnectRNPC("Zombie5");
	return 1;
}
public OnPlayerCommandText(playerid,cmdtext[])
{
	if(!strcmp("/zombie_spawn",cmdtext,true))
	{
		new Float:x,Float:y,Float:z;
		GetPlayerPos(playerid,x,y,z);
		SetPlayerPos(0,x+5,y,z);
		SetPlayerSkin(0,200);
		SetPlayerPos(1,x-5,y,z);
		SetPlayerSkin(1,200);
		SetPlayerPos(2,x+5,y+5,z);
		SetPlayerSkin(2,200);
		SetPlayerPos(3,x+5,y-5,z);
		SetPlayerSkin(3,200);
		SetPlayerPos(4,x-5,y-5,z);
		SetPlayerSkin(4,200);
		return 1;
	}
	if(!strcmp("/zombie_start",cmdtext,true))
	{
		for(new i=0;i<5;i++)
		{
			zombie_moved[i] = true;
		}
		zombie_timer = SetTimerEx("ZombieRun",1000,1,"d",playerid);
		return 1;
	}
	if(!strcmp("/zombie_stop",cmdtext,true))
	{
		KillTimer(zombie_timer);
		return 1;
	}
	return 0;
}
public OnRNPCPlaybackFinished(npcid)
{
	zombie_moved[npcid] = true;
	return 1;
}
forward ZombieRun(playerid);
public ZombieRun(playerid)
{
	new Float:x,Float:y,Float:z,Float:x1,Float:y1,Float:z1;
	GetPlayerPos(playerid,x1,y1,z1);
	for(new i=0;i<5;i++)
	{
		if(zombie_moved[i])
		{
			GetPlayerPos(i,x,y,z);
			PathFinder_FindWay(i,x,y,x1+random(6)-3,y1+random(6)-3);
			zombie_moved[i] = false;
		}
	}
	return 1;
}

OK! I found problem . I'll fix it soon.

@EDIT! OK fixed Wait a moment for update (max 30 minutes)

[RajatPawar]

I did this:

pawn Code:

PathFinder_GetNodePos(51, tx, ty, tz);
    PathFinder_FindWay(1, x, y, tx, ty);
print("Command called.");

and this:

pawn Code:

public OnPathCalculated(routeid, success, nodes[], nodes_size)
{
    new Float:X, Float:Y, Float:Z, Float:X1, Float:Y1, Float:Z1;
    print("OnPathCalculated called.");
    if(routeid == 1)
    {
        if(success)
        {
                 // .......

However, the "OnPathCalculated" message doesn't even get printed. Anything I am doing wrong?

[AIped]

I was looking for this ! Thanks man!

[pamdex]

PathFinder 0.12v released!

• New parameter in PathFinder_Init (maxnodes)
• Little bug-fix

Download in first post!

@Rajat_Pawar
NodeID to X, Y is:

Code:

new Float:x = (nodeid % 6000) - 3000;
new Float:y = (((nodeid - (x+3000)) / 6000) / -1) + 3000;

or

Code:

new Float:x = (nodeid % 6000) - 3000;
new Float:y = ((nodeid - (x+3000)) / -6000) + 3000;

X, Y to NodeID:

Code:

new nodeid = (((y - 3000) * -1) * 6000) + (x + 3000);

[Pottus]

Seems to work properly now thanks.

Suggestions - Create some sort of tolerance for along side buildings I'm finding my zombies get too close to buildings it would be nice if the path could be adjusted away from buildings by say 1.5 meters if that isn't possible then find a center average between the two buildings.

[Kyle]

What is the difference in this than RouteCalculator Plugin?

[Niko_boy]

this is so super !

[TheArcher]

MAN! Thanks a lot! Gonna try this out OMG THANKS