next »

[Hambone]

Still a little buggy, but hey, now the mouse moves on it's own!





Hambone

[Hambone]

alright so I think I fixed the corner issue, tell me if this sounds right.. please. lol

Since my directions are limited to up down left and right, to me, it makes sense that moving right should cost a little less since there are always less moves required directly right as opposed to moving down then back up?

I modified it so moving right has a smaller "g" value and ended up wit this result...




hopefully I am getting somewhere with this.  

Hambone

[Dacke]

I really, really wouldn't do that if I were you.

You've added a hack to fix a symptom in a specific scenario. But you still haven't found and fixed the underlying bug. Which means that the bug is almost guaranteed to pop up again, under different circumstances.

edit:
All you need to get an optimal path using A* is to have an admissible heuristic. Which means that the estimation of "how far am I from the goal" should always underestimate the remaining distance (or get it exactly right).

Example:
The true distance to the goal (rounding obstacles etc.) is 10 moves.
If your heuristic estimates the distance to 9 moves (or 0 or 10 moves) it is admissible.
If it estimates the distance to 11 moves (or more) it will fail to give you the optimal path.

If you only can move left/right/up/down the closest distance possible to the goal (assuming no obstacles) is the manhattan distance. Which makes it an admissible heuristic, as it will either get the correct distance or underestimate it (which is good). Which means that A* is guaranteed to give you the optimal path, using the manhattan heuristic with those movement rules.

If you don't get the optimal path (as in your previous examples) there is something wrong with your A* implementation, not with your choice of heuristic.

[gimymblert]

try theta* ?

http://files.aigamedev.com/tutorials/aap-PostProcessing.png

http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/

[Dacke]

That does look interesting, but it's not really relevant here. It's more complex and not suited for this task. Theta* seems to be good for aesthetically pleasing path planning in continuous environments. But Hambone is dealing with the simpler problem of finding an optimal path in a strictly defined grid.

[Hambone]

But Hambone is dealing with the simpler problem of finding an optimal path in a strictly defined grid.

^^ and I am still having issues with it, I feel like I should have it by now 
I am about make a fresh application and see if I can get it this time, third time is charm right??

You've added a hack to fix a symptom in a specific scenario. But you still haven't found and fixed the underlying bug. Which means that the bug is almost guaranteed to pop up again, under different circumstances.

This is absolutely correct.. Shortly after I made the post I realized that it was only solving the problem for very specific instances instead of all situations. I feel like an idiot ha... I am determined to get this!!


Hambone

[gimymblert]

That does look interesting, but it's not really relevant here. It's more complex and not suited for this task. Theta* seems to be good for aesthetically pleasing path planning in continuous environments. But Hambone is dealing with the simpler problem of finding an optimal path in a strictly defined grid.

It's for strictly define grid too, the main idea is to "backtrack" from the goal to get bee line and avoiding teh wall hugging feature seen in this thread. Similar idea can be used instead of a free directional.

Surely overkill as his behavior looks like a bias in the heuristic fct, but at the same time I wonder if is isn't an artefact on how it had implement the Manhattan evaluation, ie that for the system the little U wall hugging result from the heuristic evaluating node with the same weight. Or maybe it's when he unroll the path with the open list he didn't properly close some node (or didnt expend children correctly ie discarded child of a previous node). I bet on the Manhattan evaluation count the corner distance twice, ie met say you are at a diagonal of the goal, it would have to count Y + X, and have 3 instead of 2.

[Dacke]

Bug finding tip: try temporarily setting your heuristic to 0 (instead of using manhattan distance, but do keep "distance traveled"). In a properly implemented A* you will get an optimal path. If it still bugs out you'll know if the fault is all in the heuristic or not.

Gimym, sure, it treats the problem as a grid. But at least the way the article presents it, it's mostly about aesthetics in continuous environments. Also, I don't think it would work properly as long as the underlying A* implementation is bugged.

[gimymblert]

He should make something to visualized all expended and explored nodes

[Hambone]

So. Does anyone think the fact that my movements are 4 way, up down left and right, that this could be my issue?  Since all movemts have equal g of 10??!


Hambone

[gimymblert]

show the data

[oahda]

Why don't you just copy an existing implementation exactly instead of guessing you've done it correctly?

[dancing_dead]

Why don't you just copy an existing implementation exactly instead of guessing you've done it correctly?

how would that help him learn do this by himself? he's pretty close anyway, there's been some good advice by Dacke here on how to fix this.

[oahda]

True.

Wasn't sure whether this was for learning or one of those "pls help why don't it work i just wana mak gam not dum A*".

[Hambone]

Wasn't sure whether this was for learning or one of those "pls help why don't it work i just wana mak gam not dum A*"

School assignment, they check for copy/paste

Hambone

[oahda]

o

[Dacke]

Simple solution: create an AI that rewrites copypasted code into your coding style and adds a few minor mistakes.

More realistic approach:

1. Set your heuristic to 0. The algorithm should behave identically to Dijkstra's and you should still get an optimal path. This may give you some clues with minimal work.

2. Manually track in what order nodes are expanded. You can do this via an visualization (as by Gimym's suggestion) or by simply printing coordinates to stdout or setting breakpoints in a debugger.