Higher Cost for End Position = DLL stuck

[Maxoper]

I'm using no walls for my pathfinding, instead I have to use high cost for very unlikely positions. I use a cost value of 5-200 for those. Targeting the pathfinding to those will make the DLL loop endless. Nothing urgent though :)

[roy-t]

Is it truly endless? Because that would definitely be a bug :). Is it something you can reproduce in the viewer? In that case you could save the grid you have so I can take a look at it.

[Maxoper]

You're actually right, it won't get stuck. But it will slow down expotentially it seems. I can't use the Viewer to show this.

I'm generating my Grid (and levels) via a Images which are 180x180. For example this Image:

I set for all white areas a CellCost of Cval.

When I do: aStar.getPath(red(23,147), orange(1,1)) everything is working fine. Atleast when Cval is below 8.0f. Higher than 8.0f it expotentially grows. At 12.0f it's pretty much infinite looping in the dll.

I can set Cval to 1000.0f though, when I move to the green(11,17) dot. Now I don't need 10.0f or more as Cval actually. But at some distances and/or images I'm already getting "stuck" at 4.0f.

I would say this isn't a bug, rather a very complicated special case, that would require a lot of tweaking in code. Nevertheless, your aStar algorithm is unbeatable for me. I might have a workaround for this :)

[roy-t]

Ah I understand why this happens now. The algorithm doesn't understand that a lot of your cells have a high cost. So the heuristic is mislead. Every time it expands a cell it realizes that its guess (the manhattan distance to the end) for the remaining cost from there to the end position is wrong, and it tries another partial part.

This scenario basically turns A* into a very expensive breadth-first search. With 32400 cells that can indeed take a while :(.

Unfortunately I don't think I can do much to speed this up for you. Is there a reason why you can't just block all the cells that are white pixels in your image, and leave all cells that represent the brown pixels at a cost of 1.0f?

[Maxoper]

Yes, there is indeed a reason for this. However, most people are not particularly pleased by this. I earn my daily bread by botting games. In one of my biggest projects, the game maker did everything he could to make memory injection cheats stop working (Bots aren't such a big problem, only the poorly coded ones). That's why I wrote a very extensive pixelbot. However, position detection is not always 100% accurate. Therefore, the position can very rarely also be detected in the wall. This explains why I "may" not define walls.

Now I use a simple neural network to give the game maker no chance to pattern my Ai. The Ai is designed mostly to cover short distances, like a real player. So it really happens very rarely that the bot stands in the wall and wants to run into the wall.

Accordingly, I have now simply gone there and always check first what costs the goal has. If these are higher than 3.0f, the direct path is run in the direction of the compass.

I hope you don't have a bad conscience now. However, I wanted to explain this very special case to you in detail and why you certainly do not have to worry about it. Furthermore botting is a lucrative market, especially for people living in 2nd and 3rd world countries. Unlike many of my competitors, I also try to minimize the impact of my activities on real players. For example, no player will notice this bot in 95% of the cases.

I will close this case now and thank you very much for your explanation and help :) Best Regards