optimizing A* algorithm to fit conquer maps

[qqqqqqqqqqqw12qqqqqqq]

that is my A* algorithm working on my custom bot at some private server


it's just taking a bit more time than i've seen before on major conquer online bots like conquer ai, chrome and such

i do understand the fact that the processing on those bots were done on the bot server which was way better than my pc, yet i am still interested in looking at others source code or listen to how they implemented the logic of A* into conquer with the 18 tiles scene coming into picture

also did anyone try out concurrent dijkstra's algo? would make more sense given the 18 tile part, wouldn't it be better performance wise ?

p.s. on the picture the closed list points are circles connected with the lines (lines represent path as by jumping/walking), the square around the entity is the 18 tile points around it with validation color coded

[SuperDaft]

Check out this paper:

[qqqqqqqqqqqw12qqqqqqq]

Originally Posted by SuperDaft

Check out this paper:

loved it, kinda drifted off from my point, here is a comparison in action

what i need to optimize is the grid vs the 18 tiles jumps, all i need is an idea of how to skip some open list points

as in

assume i'm at a point called x,y
ill get all points around me in a rectangular manner limited with the 18 tiles (aka those lines from x+18 to x-18 on both y+18 and y-18 and vice versa), then ill do the same for each point i get and recalculate the g/h costs, the problem is that the number of points escalate quickly caused by the big girde of tq maps, so a long path would take up to 9 seconds on an i7 cpu, not to mention the traffic and waiting for the server to confirm the jumps

[KraHen]

Originally Posted by qqqqqqqqqqqw12qqqqqqq

so a long path would take up to 9 seconds on an i7 cpu, not to mention the traffic and waiting for the server to confirm the jumps

There is something seriously wrong with your implementation, implemented correctly A* can work with HUGE grids (well that's the entire point of the heuristics that it's based upon), very quickly.

[Xio.]

I have been using this, I don't recall where I got it from but it works like a charm with conquer maps.

Edit: It might be based on Throne's or be Throne's.

[U2_Caparzo]

Time ago i was researching too, JPS (Jump point search) specifically, that was used with the A* algorithm, i'm pretty sure that Throne used JPS so you may want to check it out for an example or even the complete code.