what's the path-finding of openkore???

[common123]

"APPLICATION AND IMPLEMENTATION OF A*ALGORITHMS IN THE GAME MAP PATH-FINDING"

does openkore just use this A*ALGORITHMS ???

i just heared that A*ALGORITHMS is a game map path-finding,

in fact i dont know what it is... and how about openkore???

[Bibian]

http://en.wikipedia.org/wiki/A*_search_algorithm

[Motivus]

OpenKore uses A*. It uses a fairly simple version coded in straight C that lacks many optimizations. OpenKore also makes use of precaluclated distance between a wall and a walkway for weighting tiles. This allows the bot to smoothly avoid lanterns and similar objects, and to walk in the middle of hallways.

The basics of A* in one convulted paragraph:

A* checks all tiles around the start tile and assigns them a value based on distance from start (actual distance), distance from finish (manhattan distance usually, although euclidan/bishop from chess can be used), and a weighting coefficient that takes in to account game tiles (like dist map for openkore). The finish difference is usually modified in some way to weight it heavily or lightly. New nodes are assigned a parent value so you know where you came from in the future. All nodes are pushed on to a binary heap (or multi-level bucket, or <other data structures>) and then the lowest value node is checked next in the same manner as the start tile. This process continues until a node is linked to the finish, or a node is the finish (depending on how it is implemented). At that point it recurses back through the nodes using their parent until the start tile is reached.

some good resources:

Amit's A* Page Good for explaining the theory in depth. If you know how to code this page has all of the information you need, but I don't reccomend using any of his code.
A* explanation I learned about A* from this page ages ago.

There is an open source pathfinding program that has an excellent A* implementation floating around. Its name escapes me. There is also a good multi threaded implementation written by someone who works at intel (I think?).

[common123]

thanks

especially,

A* explanation I

http://www.policyalmanac.org/games/aStarTutorial.htm is very amusing and suited for beginers like me

(maybe spam again,sorry)

[kali]

Which reminds me, when I was doing a miniport of openkore to c++ (which is currently in the backburner) I realized a better and more efficient pathfinding code could be made.

Maybe one of the optimizations we can make is to improve pathfinding? And actually make the stuff readable enough.

[common123]

Using Binary Heaps in A* Pathfinding

Binary Heaps

Binary heaps are very similar to the quick sort method just described, and they are often used by people who are serious about keeping their A* functions as fast as possible. In my experience, using a binary heap will speed up your pathfinding by 2-3 times on average, and more on larger maps with lots of nodes (say a map 100 x 100 nodes or more). Fair warning, however -- binary heaps are a bit tricky, and may not be worth the headache unless you are using a map with lots of nodes, where speed gains are crucial.

whole-length file here: http://www.policyalmanac.org/games/binaryHeaps.htm

but i dont know C++
....in the websites,it seems there are lots of A* path-finding open source code...
http://www.garagegames.com/index.php?se ... ry&qid=120

[sli]

There's always the awesome D*, but that's more suited towards map formats that aren't cell-based (like WoW, for example). It's also the pathfinding algo that GPS systems use. So yeah, but much for RO. A fairly agile A* algo can be implemented with pure Python in a (relatively) small about of code.

[common123]

python code is too slow

i have a python A*path-finding code that process a 60*30 map always cost about 2 second to find a path....

although, this python code have a mini-map and it's beaufiful but it's too slowly

it can work but too slow, Sli can you give me a python A* path-finding copy to me??
(you can send it with the Private message)
if you want my slow path-finding code i can send it to you from Private message or
post it here( but it's too slowly, i dont want to post it here in fact)
or your code is also not so quickly??? this python code is a website opensource code not mine
in fact...
begin:


End:

[Motivus]

I rewrote the A* implementation, I just never finished implementing it in to kore. There were some issuse with the perl part of pathfinding (movement, it'd attempt to move too far too fast) and my implementation didn't solve the crashes on larger maps with huge paths (400x400 mazes). It did speed up pathing greatly and also offered diagonal movement.

[sli]

python code is too slow

i have a python A*path-finding code that process a 60*30 map always cost about 2 second to find a path....

although, this python code have a mini-map and it's beaufiful but it's too slowly

it can work but too slow, Sli can you give me a python A* path-finding copy to me??
(you can send it with the Private message)
if you want my slow path-finding code i can send it to you from Private message or
post it here( but it's too slowly, i dont want to post it here in fact)
or your code is also not so quickly??? this python code is a website opensource code not mine

Well of course Python is going to be slower than C. The point is that A* is actually not THAT difficult to implement in just about any language.