Implement good pathfinding algorithm

[VedVid]

No description provided.

[VedVid]

Resources: roguebasin1, roguebasin2, redblobgames

[VedVid]

stack implementation for roguebasin2

[VedVid]

medium

[VedVid]

boohu's astar algorithm

[VedVid]

simple "sample algorithm" from wikipedia

[VedVid]

For now, I decided to just "bruteforcing" path from goal to the start (I can't be sure, but it looks like Dijkstra for me). It looks trivial, but SOMEHOW I can't implement it properly for a week... Still, I'd rather implement it from scratch by myself rather to use external library, because I want RAWIG to be self-contained, without any third-party libraries (except of BearLibTerminal)

[VedVid]

Example of current implementation (flawed and bugged):

https://play.golang.org/p/QwAnARS0Ndx

[VedVid]

Fixed implementation:

https://play.golang.org/p/pxJx4unbOz1

[VedVid]

Creating graph is finally done! Commit history is very ugly, but I'm pleased with final effect.

TODO:

• moveTowardsPath should move creature, not create a graph
• comments!
• maybe graph should not be re-calculated, if target remains the same?

[VedVid]

backtracking in progress...

[VedVid]

Tests failing.

code: https://play.golang.org/p/JqCWKPiOymH

problems:

• "T" is creating larger distance from "@" instead of approaching it; it looks like fleeing
• even if it's fleeing, it's flawed, because it stops on (19, 19)

[VedVid]

both flaws are fixed now

[VedVid]

TODO: #33 #34 #35

[VedVid]

#33 done!

[VedVid]

TODO: #34 #35 #36

[VedVid]

#34 done by 7943a9c and edec91d

#36 done by edec91d

#35 postponed

[VedVid]

Finally, merged into development branch by 1e22dda