New pathfinding A* algorithm review

[Henrybk]

This is the reviewed and cleaned branch of the pathfinding algorithm changes.

Openkore uses an old A* code for pathfinding, it has a few problems:

1 - It is not capable of calculating diagonal movement.
2 - Uses only distance to walls to calculate cells weighting.
3 - Is not capable of dynamic weight changes of cells since the weight is hard coded in distance to walls.
4 - Is not guaranteed to find the shortest paths.
5 - runfromTarget, attackCheckLOS and AttackCanSnipe don't work.

This branch fixes a few isses.

Features:

1 - Uses new simplified fld2 files
2 - Uses .weight files based on .dist files instead of .dist files, allowing custom static or dynamic weight maps (avoid mvps, non-walking mobs, dangerous map areas)
3 - Correctly uses diagonals, using weight 1.4 that of ortogonal moving
4 - Uses diagonal distance heuristic, which is the most appropriate for ragnarok maps
5 - Is guaranteed to always find the shortest / best path since it does not limit openlist
6- Fixes runfromTarget, attackCheckLOS and AttackCanSnipe
7- Corretly predicts the time to walk a given distance, preventing a few timeouts

Edit: Most of the changes were ideas from here: http://forums.openkore.com/viewtopic.php?f=36&t=1350

this pull fixes #2546.

This pull is a continuation of #1684.

The code was based on Sven Konig publications (Father of most of the pathfinding algorithms used today): http://idm-lab.org/publications.html

[Xmpeshka]

Thx - it's works, but in xkore1 i have same microfreezes as at this video https://youtu.be/MWEnuPa0D0U On rms on xkore2 - all was ok

[Henrybk]

@Xmpeshka Thanks for the reply, I have made a lot of changes since you made this video, would you be able to test again in xkore1 to see if it persists?

[Xmpeshka]

i downloaded Remake-routing-review today, test it on rms server in xkore 2 - al was ok then i change servertypes for my server and run in xkore 1 - got microfreezes

it looks same if use master-branch and set routestep from default 15 to 7(as you use)

[Henrybk]

@Xmpeshka Have you tried increasing this PR route_step? you should still be able to use values as high as 14, I only decreased it for compatibility issues, but 10 should still be very well handled.

[Xmpeshka]

I try route_step 9 - still got freezing At 10+ - kore don't move - stay about a minute - then error - coordinates is not walkable

[Xmpeshka]

Upd: with PR - 9 - freeses a bit lower, bun 10+ kore can't move (from macro move command) Upd2: with pr14 - it can move near (about 3-4 cells) but if move x y = next location(new zone) - it stay and got error

[Xmpeshka]

is it any way randomize route ?- don't use every time best(shortest) way because if many bots on a location - all of them going step by step in certain sites of location - it looks like big train of bots )

[Henrybk]

@Xmpeshka This is an old problem in pathfinding (example: https://forum.unity.com/threads/navmesh-agent-introduce-noise-into-path.166183/). What should be easy to do is to set an option in in the pathfinding to call to add a bit of noise (randomness) in the calculation, so all paths should look similar but not the same.

[Xmpeshka]

If it possible - it will be a good to impiment it there. Wigh noise config key =))

[Xmpeshka]

Rms test server - route step14 step 13 _ On rms - it stops moving after 12/13+ On my server stops after 10+

[Henrybk]

@Xmpeshka O thanks for the prints. Yeah, there is a check that makes route_step > 10 impossible, I can't change it right now but you can change it yourself in your branch and test it.

On Task::Route, in sub iterate at line 451 change: if (blockDistance(\%nextPos, $current_pos) > 10) { to: if (blockDistance(\%nextPos, $current_pos) > xxxxxxxx) { 'xxxxxxxx' being the route_step you want to test +1.

[Xmpeshka]

thx - it works )

p.s. have u any idea - how fix this ? =)

[Xmpeshka]

another bug: sometimes kore randomly stand for about 10 secs in clean fild then - works normal some time - then stand again - this bug also have a master-branch - but not so often (2-10 times in 5 min)

[Henrybk]

That is just lag, the move packet will be re-sent until the server responds.

[Xmpeshka]

That is just lag, the move packet will be re-sent until the server responds.

if i move directly from client - all is ok, not the lag if i print "ai clear" kore starts moving until next stop

[hubertyang88]

1735 freeze problem?

[Xmpeshka]

No, screenshot upper, no mapchange or tele, after random time - kore stops in random place on map then after 5-10 secs continue route

[Xmpeshka]

got a stuck with attack ) and still got random move stucks

[hubertyang88]

I try to run this version , https://github.com/OpenKore/openkore/blob/cee04dc7bb9d940c7e4dd03fd11f9f080275ad47/

But I get error ,and openkore fail to start , what should I do? Error message: Can't call method "closestWalkableSpot" on an undefined value at src/Misc.pm line 3712.

Stack trace: Can't call method "closestWalkableSpot" on an undefined value at src/Misc.pm line 3712. at src/Interface/Wx.pm line 163 Interface::Wx::mainLoop('Interface::Wx=HASH(0x61945fc)') called at openkore.pl line 97 main::__start() called at start.pl line 136

line of error: my %dest = %{$mapPortals{$map}{$portal}};

• my $closest_start = $field->closestWalkableSpot(\%start, 1); my $closest_dest = $field->closestWalkableSpot(\%dest, 1);

[alisonrag]

You should use the branch related to this pull Dont use versions related to master

[hubertyang88]

You should use the branch related to this pull Dont use versions related to master

@alisonrag How to do that? I try to download zip at Remake-routing-review，it seems worse . So I found the link in "Files changed" --> "view file" , there is a link https://github.com/OpenKore/openkore/blob/cee04dc7bb9d940c7e4dd03fd11f9f080275ad47/ and I use DownGit to download .. What is wrong?

[alisonrag]

https://github.com/OpenKore/openkore/archive/Remake-routing-review.zip

[hubertyang88]

@alisonrag I try your link , the error remains , and it happened at compiling the portals, So I copy portals and portallos file to avoid this step , and I get an other error It seems some file are missed in the zip file I download...

new error: Error message: Undefined subroutine &Utils::makeWeightMap called at src/Field.pm line 645. Stack trace: Undefined subroutine &Utils::makeWeightMap called at src/Field.pm line 645. at src/Interface/Wx.pm line 163 Interface::Wx::mainLoop('Interface::Wx=HASH(0x5309b44)') called at openkore.pl line 97 main::__start() called at start.pl line 136

error my $f;

• $self->{weightMap} = Utils::makeWeightMap($self->{dstMap}, $width, $height); if (open($f, ">", $weightFile)) {

[Xmpeshka]

i decide test it again ) and got another stuck at 3 different "workers" ) when i typed "ai clear" fabre was killed and "worker" continue moving and attacking normaly

And old situation - stays and not moving, when agro fabre attacks - "worker" kill it After about 30sec-1minute - worker contiune moving buy himself or manualy with "ai clear"

or another situation - stays and do nothing only eating pots and killing agro fabre that attacks

[Henrybk]

@Xmpeshka Sorry for the late answer. Yes, I was able to identify not one, but a few, bugs in the way my code decides to approach a target while attacking, I am currently testing the fix. Thanks for testing.

[Xmpeshka]

When i first tried to run this build on rms server i see that at route_step 7 - bot moves smoothly but on euro/rro it moves jerky - step 15 solve this problem but got random "afk" (don't know if it was on rms, cause i don't test on rms so long)

Also if bot got agi up on rro/euro with step 15 and master branch -movement becomes jerking, step 17 - "fix" it, but random afk appears(sometimes it happens a bit w step 15 too) - but not so long as in your build

[Henrybk]

@Xmpeshka All the attack bugs should be fixed new, I ran it for about 6 hours with a meele character without any issues, both ranged characters and slaves need more testing though.

[Xmpeshka]

got a move bug in 7 min from start on 2 windows https://youtu.be/riA9gjDTXdk and loot taking looks strange(on last poring) tested w route_step 17, cause on step 7 - bot cant move normal and also strange movement https://youtu.be/4SiZpCeqMeo looks like default ro lags, but on master branch i never see that

[Henrybk]

Hello @Xmpeshka, thanks again for testing, I had forgotten to change attackDistance and attackMaxDistance in config.txt to 1, as they should always be for meele characters. Please use route_step 7 as it is the one that best resembles the normal openkore behaviour. I also added a new config.txt key attackUpdateMonsterPos that should fix position lag, please make sure your config.txt is uptodate. Thanks again.

[Xmpeshka]

i can't use step 7 on rro\euro - cause it can't move normal )) https://youtu.be/A1eeHoxDn8I - what happens if i use step 7 ) attackUpdateMonsterPos was 1 - i took clean new config from this branch a bit later will test for "lags" w attackMaxDistance 1

[Henrybk]

That is very strange, it seems to be only moving about 3 or 4 cells at a time, can you make a video of the console and character with route_step 7 as you did before? Thanks

[Xmpeshka]

https://youtu.be/QJHPwGWcJgs done

[Henrybk]

Seems like the route messages are been filtered, this is how it should look like, with the "Route You" debugs.

[Xmpeshka]

https://youtu.be/EhRBD6pVlg8 sorry, my fault - it was set in start macro

[Henrybk]

Now the routing algorithm should be a bit more responsive and you should be able to use route_step up to 10 (the max I tested) without issues.

[Xmpeshka]

I replacerd all route.pm file and add line in timeouts Nothing happens ( steps lower than 14 - jerky moving - this shit on euro/rro. When i fitst started it on rms - movement w step 7 was normal step 14 stays and "smoking": And at this moment when new point was found for route it started moving and then stand again about ~50% of founded routes w step 14+(what can be usable on euro\rro) leads to stuck

[Henrybk]

Well, this has been a wild ride, there were a few reference bugs in route.pm and a line of code was blocking route steps above 13 to work, this last commit should fix that. Thanks for your patience.

[Xmpeshka]

stuck on mapRoute and same on randomRoute

[Xmpeshka]

Got a long stuck and after that movement conrinues

p.s. it became better - still got stucks on route - but it "self fixes in 3-4 secs"

[Henrybk]

The code that tried to unstuck was not working, it now works, sometimes the move pair (start cell and destination cell) is just not a valid one, and sending the move packet won't work, I had this happen in new_1-3, moving from 64,139 to 79,138, the server will just ignore the packet, this happens because there is a "Field of view" check that also uses the distance between cells in the server. At the moment I don't know exactly how it works.

This should happen more the higher route_step is.

[Xmpeshka]

random route atm, is it possible to do it faster or less attempts ?

[Henrybk]

Yes, but the timeout key is not doing anything even in the normal openkore master right now, I'll fix it in a minute

[Xmpeshka]

and another long stuck at attack

[Henrybk]

Now these timeout keys should work:

ai_move_retry 0.25 - The time to wait between move packet sends ai_move_giveup 1 - The time to wait before giving up the move packet

Maybe now you would have a better experience trying route_step 9~11 instead of 15

Video I made now: https://www.youtube.com/watch?v=0ZSuahOG1Hc

[Xmpeshka]

ai_move_retry 0.15 + step 9 now looks normal(0.25 at horisontal movement was a little jerky ) thank u

[Henrybk]

It is I that must thank you for testing so much of my code and so many times haha.

Let me know if you find anything

[Xmpeshka]

i also have a feature request: adjust distance that random walk chose point to move + option don't calc a new route after killing mob before old point wasn't reached. For exaple start from one corner of map and move continiously about 300 cells way, killing mobs during this trip, then calc a new long route...

Now kore sometimes cals route like chaotic random ) and bot runing from point to point in one part of map, not like player wiil.

[Henrybk]

I believe that was made that way for a reason, but I don't remember what reason exactly. This can be achieved by using plugins, I have made a in the past plugin that does that actually, but you had to manually insert the desired route, there is also the waypoints plugin, but I never used it.

But the 2 features you asked could be implemented using config keys with a little code change.

[Xmpeshka]

https://youtu.be/FTQpZkJwTqI a strange "dancing" movement https://youtu.be/I4VtVQp9roA overall video, where we can se thar random routes decide where to go very strande, prefer south part of map

[Henrybk]

Both videos are set to private