AI 2008 fld2 and PathFinding algorithm

[Henrybk]

As some of you may know I have been working on writting a new pathfinding code for openkore for quite a while, I believe today I finally got it working and decided to PR it so other developers can take a look.

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 - Uses about 42% less time to calculate a route
7- Fixes runfromTarget, attackCheckLOS and AttackCanSnipe
8- Corretly predicts the time to walk a given distance, preventing a few timeouts

benchmark of current algorithm: https://gyazo.com/cd3adf01a6af0b022e5e57a4010c7064

benchmark of my algorithm: https://gyazo.com/2359320cab8587a1e9078558b99ac4d9

My benchmark consists of all the portalslos paths plus 20 randomwalks on all RO maps.

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

this pull fixes #2546

[c4c1n6kr3m1]

my problem untill now is all bots walk on the same path, so obvious, only 0 or 1 for weight need better option for that

[Henrybk]

That’s the idea with custom dynamic weight maps, it would be pretty easy to write a plugin to make bots walk on diferent but short paths, just add randomly 5~15 weight to all walkable cells on the mao when the map is loaded

[c4c1n6kr3m1]

this is awesome,
hope you give example for the plugin Random path weight and better Line of Sight will make better bot

[Henrybk]

Just made some new benchmarks and found that my code is almost twice as fast

[c4c1n6kr3m1]

just tried fresh download this "Remake-routing" branch

first run with win7 32 bit 1st error crash when compiling portals 2nd error

Undefined subroutine &Utils::makeWeightMap called at src/Field.pm line 336.

@Henrybk ???

[Henrybk]

@c4c1n6kr3m1 I can't find a way to compile XSTools in windows, so the code will only work on linux OS for now

[Xmpeshka]

Getting an error when compiling portals,

Can't call method "isWalkable" on an undefined value at src/Misc.pm line 772.

        foreach my $z (@spots) {
*           next if (!$field->isWalkable(($pos->{x} + $z->[0]), ($pos->{y} + $z->[1])));
            $pos->{x} += $z->[0]; 

[Henrybk]

This PR has been updated and should now be working if properly compiled. I have also updated and compressed all fld2 files.

[Xmpeshka]

@Henrybk Help =) Can u compile xstools for your bild. I trying compile it by get errors after replacing deps from 2402, dll was compiled but i get errors Free to wrong pool f88e80 not 4000 at src pathfinding.pm

If it's possible - it will be good present fo xmas - working kore with your algorithm )

[JpnHub]

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)

Would it be possible to create a small and simple plugin to showcase the dynamic real time weight modifications?

As from my current testing, everything seems to be an overall huge improvement in both speed and efficiency, but the dynamic modification of the weight system is a tad bit confusing to understand from your code alone, which is a shame considering the immense improvements it could bring alongside with itself.

[Henrybk]

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)

Would it be possible to create a small and simple plugin to showcase the dynamic real time weight modifications?

As from my current testing, everything seems to be an overall huge improvement in both speed and efficiency, but the dynamic modification of the weight system is a tad bit confusing to understand from your code alone, which is a shame considering the immense improvements it could bring alongside with itself.

So, the branch which was used for this PR is able of dynamic path modification, but not efficiently, you would need to recalculate all the remaining path to the destination. This branch uses A star for its calculations, I have 3 others branches of this one which improve exactly on the dynamic pathing, one uses Lifelong Planing A star, another one uses D star Lite and the third is a incomplete unfinished version of a Moving Target D star Lite implementation.

On the D star Lite branch I use a plugin (https://github.com/Henrybk/openkore/blob/D_star_lite_field_cell_increase/plugins/DStarLiteAvoid.pl) to add obstacles to the weight map, which get resolved by Task::Route, which makes Task::Pathfinding recalculate only the steps necessary for the obstacle to be avoided.

Here is a gif of this method working to avoid a monster: https://i.gyazo.com/a37fbb7b59a16099c9b9b30df0f51bc5.mp4

[eprabotmesmo]

Estou querendo testar esse patch mais está dando problema para compilar os portais se eu tirar todos os mapas que dão problema ele funciona @Henrybk tem ideia do que possa está ocasionando o erro? os mapas que lembro de cabeça que dão erro são "har_in01, rockrdg1, juperos_01, lighthalzen".

obs.: Já tentei extrair os mesmo é converter para fl2 não deu certo. obs2.: No linux o problema não existe.

[Henrybk]

Updated branch to master, fixed all remaining known bugs, made a few changes to make it about 5% faster, made a lot of code cleaning and added some comments.

[Henrybk]

I also have a branch in my fork in which I applied @lututui PR #2402 so I can compile it in windows. Branch: https://github.com/Henrybk/openkore/tree/Routing-clen%2Bbuild

[Xmpeshka]

Crashes on compiling portals

[Henrybk]

@Xmpeshka Did you compile xstools properly? You must have Python - 2.7.1 (x86) Perl Strawberry - 5.28 (x86) C compiler while using the branch with lututui's build changes and use gmake while on the openkore root directory in cmd/powershell.

Otherwise if you want to test just just install Perl Strawberry - 5.28 (x86) and I'll compile xstools and add the compiled dlls to the branch.

Edit: I added the compiled dlls into branch https://github.com/Henrybk/openkore/tree/Routing-clen%2Bbuild

[Xmpeshka]

same situation on another pc with yours precompiled dlls strawbery x86 5.28.1.1 starting compiling portals and crashes on the same place

on pc where i compiling myself i use 5.28.1.1+python+minigw

[Henrybk]

Strange, I just compiled portalsLOS here without issues. Could you please translate the error message you are getting?

[Xmpeshka]

Standard windows error like this Starting openkore - using openkore.pl

[Xmpeshka]

deleted strings aldeg_cas05 from portals.txt and portals compiled normaly

[Henrybk]

Can you provide the portals.txt you are using? I can compile aldeg_cas05 normally. Also, just to be sure, are you using openkore.pl instead of the .exe's?

[Xmpeshka]

using portals from branch, server -localhost for test, launching openkore.pl

[Henrybk]

thanks for testing, I'll check into that error

[Henrybk]

Activating debug doesn't show anything in the console?

[Xmpeshka]

1 )new problem - no moving: attack, west 5, randomRouting - Char stays on ground like a stone =) if monsters appearts near char - attacks normal and take loot normal

[Xmpeshka]

Activating debug doesn't show anything in the console?

then crashes

[Henrybk]

new problem - no moving: attack, west 5, randomRouting - Char stays on ground like a stone =)

Fixed this in the last commit in both branches, I had forgotten to invert the order of the array of coordinates returned to Route.pm from Pathfinding.pm

[Xmpeshka]

Compiled new dll: west east comands and, attack with move to target - works move x y, randomroute - don't work

Coordinates was 53 93(53 123 is walkable - not wall etc)

west 15 = move 1 move 1 block... west 20 - stays

[Henrybk]

@Xmpeshka Fixed the map compilation crash, I had not implemented a failsafe for when the user tries to solve a path with invalid coordinates.

Turns out the portal aldeg_cas05 188 49 aldeg_cas05 165 288 cannot exist, since the map is only 240x240.

Edit: also I was able to use move x y and randomWalk without any issues.

[Xmpeshka]

@Xmpeshka Fixed the map compilation crash, I had not implemented a failsafe for when the user tries to solve a path with invalid coordinates.

Turns out the portal aldeg_cas05 188 49 aldeg_cas05 165 288 cannot exist, since the map is only 240x240.

Edit: also I was able to use move x y and randomWalk without any issues.

My fault - forgot about route_Step 7 and used my own conf files Working normal - but little bug on my conf i have a eventMacro that talks in noob zone

    do ai manual
    do move 55 110
    do move 55 110
    do talknpc 53 114 c c c c c c c c n
    pause &rand(2,5)
    do move 147 112
    pause &rand(5,10)
    do move 100 25
        ....

Kore don't talk with npc and walks next

[Mar 27 22:42:15 2019.57] Move You - (re)trying
[Mar 27 22:42:15 2019.69] You're moving from (53, 111) to (55, 110) - distance 2.2
[Mar 27 22:42:16 2019.12] Move You - (re)trying
[Mar 27 22:42:16 2019.23] You're moving from (55, 110) to (55, 110) - distance 0.0
[Mar 27 22:42:16 2019.23] Move You - done
[Mar 27 22:42:16 2019.62] new_2-1 148 112=new_2-2 100 9, 113
[Mar 27 22:42:16 2019.62] new_2-2 100 6=new_2-1 144 112, 136
[Mar 27 22:42:16 2019.63] Distance to portal (new_2-1 148 112=new_2-2 100 9) is 93
[Mar 27 22:42:16 2019.63] Attempting to teleport near portal, try #1
[Mar 27 22:42:16 2019.64] You don't have the Teleport skill or a Fly Wing
[Mar 27 22:42:16 2019.70] Move You - (re)trying
[Mar 27 22:42:16 2019.81] You're moving from (55, 110) to (63, 111) - distance 8.1
[Mar 27 22:42:17 2019.24] Move You - (re)trying
[Mar 27 22:42:17 2019.30] You're moving from (58, 111) to (63, 111) - distance 5.0
[Mar 27 22:42:17 2019.30] Move You - done
[Mar 27 22:42:17 2019.31] Move You - (re)trying
[Mar 27 22:42:17 2019.84] Move You - (re)trying
[Mar 27 22:42:17 2019.90] You're moving from (62, 111) to (67, 111) - distance 5.0
[Mar 27 22:42:18 2019.33] Move You - timeout

I used tables, control, and plugins folder from my working build of kore - portals was recompiled for my server route_teleport is set to 0

[Henrybk]

Thanks again for testing, I will take a look at that when I get the time

[Henrybk]

I just tested it with you macro and was able to talk to sprakki normally

https://i.gyazo.com/ba0c3ba35725ef8f47a8dd9c8aded849.png

[Xmpeshka]

hmm it's called from another automacro - but i copied by all folders from my main kore excluding src - nothing changes in config except routeStep if at this moment manualy wrote in console move 55 110 - it's talk. same problem with all novice ground - kore skips talking with an npcs and trying teleport from not existing(fake) portals and finaly stopts in this point 126 106 we have no portal there -i compiles portals with related my server portals.txt ` ------------------ AI Sequence ------------------- 0: route

1: eventMacro {mapChanged=>'1553720616.04922'}

---

` Same situation with taking my fld files and using them after converting to fld2 I tested another macroses in city etc and it seems that they working normal

[eprabotmesmo]

whenever you will use the locking autostorage

[Henrybk]

@eprabotmesmo Firstly, did you use the compiled branch or did you compile it yourself? Are you using your own config files or the ones on my branch? Did you use openkore.pl? If so, can you post another test with debug on?

[Xmpeshka]

also tested thief quests - macroses works normaly. at this moment bug only with newbie zone. Also strange attemps to teleport from portal at the start of newzone - there is one npc and bridge =) no portals etc - standart zone of official revoserver

[Xmpeshka]

also some little bug ) w taking loot

[eprabotmesmo]

@eprabotmesmo Firstly, did you use the compiled branch or did you compile it yourself? Are you using your own config files or the ones on my branch? Did you use openkore.pl? If so, can you post another test with debug on? I using your branch files

[sctnightcore]

@Xmpeshka test with openkore not icekore / windkore !

[Xmpeshka]

@Xmpeshka test with openkore not icekore / windkore !

waht difference ? i take openkore-Routing-clen-build - and changed only network packets, tables, and injection part - all other src are from this branch

[sctnightcore]

@Xmpeshka I think it's different.

[Xmpeshka]

@Xmpeshka I think it's different.

u can test it on windkore - it will be a good expirience - maybe i doing something wrong

[Xmpeshka]

Tested with the last master branch(with network changes affects my server) - all ok with macros.

[Henrybk]

Tested with the last master branch(with network changes affects my server) - all ok with macros.

Thanks again for testing.

[Henrybk]

@eprabotmesmo Firstly, did you use the compiled branch or did you compile it yourself? Are you using your own config files or the ones on my branch? Did you use openkore.pl? If so, can you post another test with debug on? I using your branch files

I'll take a look at that, thanks for testing and reporting.

[Henrybk]

also some little bug ) w taking loot

@eprabotmesmo Firstly, did you use the compiled branch or did you compile it yourself? Are you using your own config files or the ones on my branch? Did you use openkore.pl? If so, can you post another test with debug on? I using your branch files

Last commit should have fixed both of those issues, I updated both branches.

pickup: https://gyazo.com/cdd51cd2c28f3b7a83cf338ec3a4df72

Storage: https://gyazo.com/0af1c065046cc7836aa580d72212ad33

[Henrybk]

These last changes should be the last ones unless someone finds any more bugs. In them I updated to master, which now uses lututui's build changes branch, so no need anymore of using the other branch to test. I also changed the base weight of any cell to 0, so it won't affect the best route calculation (which uses 10 for ortogonal and 14 for diagonal moves), walls now use weight -1. I also commented some error messages because they would be too common since openkore calls a lot of dumb pathfinding requests.

[Xmpeshka]

https://youtu.be/Cl_JrEbcsQc same shit on rms test server - using untouched remake-routing branch - only eventmacro.txt added

probleb with pathfinding - it moving to 55 110 - goes in portal and then goes back, then only talks with npc, same problem was in prontera city - it goes to prt_in - then prontera prt_in...

[Xmpeshka]

Tested again, same bugs ( AutoEventmacro: if (($.map == "new_1-2") || ($.map == "new_2-2") || ($.map == "new_3-2") || ($.map == "new_4-2") || ($.map == "new_5-2")) call StartTheGame

macro StartTheGame {
    do conf QuestSteep none
    do ai manual
    do move 55 110
    do move 55 110
    do talknpc 53 114 c c c c c c c c n
    pause &rand(2,5)
    do move 147 112
    pause &rand(5,10)
    do move 100 25
    do move 100 25
    do talknpc 100 29 c c c r0 c c n
    pause &rand(5,10)
    do move 100 100
    do move 100 100
    do talknpc 100 105 c c c c c c c c c c c c c n

[Glikadin]

Hello. Today i am testing remake-routing.

After i fixed

routeweights.txt

PORTAL 100

The bot finds the way well But have problem: During movement, the bot constantly pauses (default timeouts.txt) ((( Video of my testing: https://youtu.be/MWEnuPa0D0U