[Y_Less]

Quote:

Originally Posted by Gamer_Z You are seriously kidding me.... linux does not have a standard parallelism library, that's the problem..

Err, pthreads?

[Gamer_Z]

Quote:

Originally Posted by Y_Less Err, pthreads?

My bad, mistake, I ment parallel containers (library)..

People complain about the fact I use Intel Thread Building Blocks... yet I don't know any better alternatives, and I doubt there are..).

[pamdex]

PathFinder 0.13v released!

• New optional parameter in PathFinder_FindWay (step_limit)

Download and more info in first post.

[Mauzen]

@pamdex: Are you still working on this?

I experimented a bit with this. Using a buffered mapandreas mode instead of the nobuffer one at least doubles the speed (tested on a ssd). For slower HDDs the effect is even greater.
I also experimented with a pretty new in science A* subtype and managed to get speeds 4-5 times faster than with the standard one using buffered mode, so a 10x speed boost is realistic. Had some problems with the algorithm though, it is not suitable for release.

[pamdex]

So... I have a test version of completly rewritten PathFinder (full OOP).
It is using FULL or NO BUFFER MODE - new MapAdreas 1.2.1) and my own algorithm implementation (djikstra styled) - it's working perfectly (Linux & Windows) and very fast.

~iPhone

[pamdex]

I'll release fixed test version of PathFinder this week.

@EDIT
I'm back after some problems with my old computer.

[Pottus]

Hmm hopefully it works better the old version failed for me when trying to update 25+ NPCs.

[RiqueP]

Very nice

[pamdex]

PathFinder 1.0 RC 2 released!

• completely rewritten code

Download -> first post. If you using old version of PathFinder, please read first post!

[iFarbod]

Is this plugin's a good choice to making NPC Taxi Drivers? I Want to make NPC Taxi drivers that drive to the target, (No matter RNPC or FCNPC):

1. We enter the taxi as passenger. (G)
2. We have 10 seconds to choose a waypoint on the map. If you don't pick the target you'll be forced to exit the taxi (removePlayerFromVehicle) (Press ESC, -> Map, Right Click on the destination).
3. Then this plugin must find the way, and NPC Must drive smoothly to there.
4. Once reached destination, you'll exit the Taxi, and it will subtract the money from the player.

Is Possible?

[pamdex]

For bots driving on the streets you should use:
https://sampforum.blast.hk/showthread.php?pid=1475418#pid1475418

My plugin can be used for walking bots, but not for driving.

[iFarbod]

Quote:

Originally Posted by pamdex My plugin can be used for walking bots, but not for driving.

Thanks, this is useful too. (At least for me)

[Mauzen]

Great, good to see this update. Ill test it soon, I recently had an idea for a small script that works with this plugin.

[Riddick94]

Mauzen, I think it's a good time to update RNPC with the latest version of PathFinder; maybe just combine them together like Pamdex did once. Anyway, for now I will try to use both at the same time, still good to see updates.

[Mauzen]

Its always a good time for a update of RNPC, I wish I could motivate myself more often to work on it
Yep, I think its time for better support for the pathfinding plugin now, Ill also add that to my list. At least the stuttering movement should get fixed, I edited the movements and fixed the problem that caused them in my dev version already.
I wont include the plugin with RNPC however, it will probably just offer functions for automated movements that use it. Its always better to keep plugins independent from each other, so they can be updated separately.
Ill contact you, pamdex, for that when I proceeded further with it.

[Mauzen]

I did a small test.
1.0 is really quick in most cases, faster than the previous versions.
Though when the target is unreachable (e.g. a roof of a house) it seems to be very slow, sometimes taking several seconds.
Maybe theres a loophole or something, as its taking much longer than it should to hit the 2000 steps limit, compared to how long a successful 100 step path takes.

Anyways, good job, the difference to the previous versions is really noticeable.

[Mauzen]

Quote:

Originally Posted by Gamer_Z It's kinda explainable, as the A* algorithm keeps searching until a paths is found OR all nodes have been accessed, considering the gta map is about 6000x6000m, divided into small pieces, that can take some little more memory and CPU to process. As for Dijkstra algorithm it doesn't matter, the searching time is consistent because it always checks all nodes.

It actually only checks nodes that are connected to the target/start.
Nodes are generated in-time, as it recursively adds neighbors to the pool. A closed and disconencted roof would only contain a tiny amount of nodes compared to an open road, so there isnt much to check and it should rather be faster.

I didnt take a look at his algorithm yet in the new version, but it wasnt such a drastic difference in the previous version. So Id guess theres some kind of bug.

Edit: Manual backtracking seems to help in case of small disconnected areas. Swapping the start and destination, so it finds the way the other way round, and so will run out of nodes much faster when starting in the disconnected area. Just needs some extra attention as youll need to add the final node / original target point yourself, as the starting point of the calculation normally doesnt have to be added to the resulting path nodes.
Depends on what you use it for though which way would be faster on average.

[pamdex]

Quote:

Originally Posted by Mauzen It actually only checks nodes that are connected to the target/start. Nodes are generated in-time, as it recursively adds neighbors to the pool. A closed and disconencted roof would only contain a tiny amount of nodes compared to an open road, so there isnt much to check and it should rather be faster. I didnt take a look at his algorithm yet in the new version, but it wasnt such a drastic difference in the previous version. So Id guess theres some kind of bug.

I'll add little code, which will check start and end node. New algorithm creates more realistic path.
I'll create new video with NPC path finding test.

Any others bugs?

[Mauzen]

Quote:

Originally Posted by pamdex I'll add little code, which will check start and end node. New algorithm creates more realistic path. I'll create new video with NPC path finding test. Any others bugs?

Apart from that the plugins works absolutely fine so far.

Ive recently been thinking about an alternative method for the former MapSearchNode::IsBlocked (that now is integrated into the algorithm)
Its not much work to get MapAndreas data and compare some floats, but that little work sums up for long paths, as it gets checked thousands of times.
Do you think it would help to use a specially generated collision map instead of the mapandreas data?
My current idea looks like that: The collision map would consist of 6000x6000x1 bit. Imagine this grid to be between the mapandreas grid, so a grid at a certain position would determine if the path from the two adjacent fields the bit lays between can be passed. This would reduce the current check (get two mapandreas floats, subtract them, check the absolute result against the max height difference) to just a very few basic operations (get the bit from the collision map, check if it is true). It would actually buffer these height checks, saving the time for solving them later, at costs of ram. As all those IsBlocked checks are a major part of the algorithm, I guess it could give a noticeable performance boost.
The collision map itself wouldnt consume much ram (6000x6000x1 bit = ~3.6 MB), and could e.g. be generated and provided (and updated when mapandreas data is changed) by mapandreas. Maybe ill give this a try soon. Actually I thought about this as it would also allow blocking paths when theres no mapandreas height difference (e.g. thin walls, fences, doors, etc)

Edit: Its actually 6000x6000x2 bits when also considering diagonal paths, but thats still no dramatic ram increase.

[Crayder]

Imagine this combined with Pottus's ColAndreas... The future is at hand, I wonder who will be the first to try it... :P