Comments (4)
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.
from astar.
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 :)
from astar.
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?
from astar.
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
from astar.
Related Issues (20)
- Index was outside the bounds of the array error HOT 2
- Memory allocation number is unacceptable and library author ignoring the concerns HOT 5
- Considering the size of the agent
- Finding closest path to unreachable end cell HOT 4
- Deterministic? HOT 2
- Info: v2 WIP version available on Master HOT 2
- Hidden Connect method HOT 3
- Documentation / IntelliSense support HOT 5
- Isometric Support HOT 1
- Coming to v3 HOT 3
- Path. HOT 3
- No issue just a question. HOT 3
- Saving and loading graphs HOT 7
- TODO: release new minor version with save/load changes HOT 1
- just question HOT 2
- Question: GPS coordinates HOT 3
- Question HOT 1
- Explanation on how velocity is used HOT 6
- Question : Bidirectional graph search HOT 1
- Question: obstacles HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from astar.