search

jas14 / amity-apcs-ge-2011

Automatically exported from code.google.com/p/amity-apcs-ge-2011
0 stars 0 forks source link

A* Algorithm #21

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
Ok so we need to start working on the A* Algorithm..

Links:
http://stackoverflow.com/questions/1970453/algorithm-and-data-structure-for-solv
ing-the-game-globs-flood-fill-floodit

http://stackoverflow.com/questions/1430962/how-to-optimally-solve-the-flood-fill
-puzzle

In the second link, 3rd post down is the basic idea i think we should use, 
however for the estimate on the number of moves we should use Mike Z's diagonal 
method.

Please read both of the links if you havn't already.

Original issue reported on code.google.com by drdaniel...@gmail.com on 24 Mar 2011 at 7:13

GoogleCodeExporter commented 9 years ago 
incidentally, we should probably do only sqrt 2*max/2 or max/2 iterations. of 
course, giving modified A* a good estimate might call for the whole thing.

Original comment by sreservoir on 24 Mar 2011 at 7:22

GoogleCodeExporter commented 9 years ago 
lets just implement it as is. honestly 200ms is pretty decent for the beginning 
lol. High level optimizations before low level.

Original comment by drdaniel...@gmail.com on 24 Mar 2011 at 8:05

GoogleCodeExporter commented 9 years ago 
[deleted comment]
GoogleCodeExporter commented 9 years ago 
I am finding conflicting information.

"As long as your heuristic doesn't underestimate costs, the first solution you 
find is guaranteed to be optimal."

"In order for a heuristic to be admissible to the search problem, the estimated 
cost must always be lower than or equal to the actual cost of reaching the goal 
state."

Original comment by drdaniel...@gmail.com on 24 Mar 2011 at 8:18

GoogleCodeExporter commented 9 years ago 
http://www.youtube.com/watch?v=Kw8AMmyc6vg
We are going to trust wikipedia and this video. Also, for the heuristic the x+y 
as this video suggests seems reasonable.

I think we should progress to the bottom-right corner as that is the last area 
to be selected by brute-force. Furthermore, once we get there brute-force 
should take over as it is very efficient for end-situations.

Original comment by drdaniel...@gmail.com on 24 Mar 2011 at 8:34

GoogleCodeExporter commented 9 years ago 
Not really conflicting.  Put the two statements together and you get that we 
should try to get an exact measure of the cost for our solution to be optimal; 
however, if an exact cost cannot be obtained, we absolutely CANNOT overestimate 
the cost or the A* search algorithm won't work.  I'm not sure if it's possible 
to obtain an exact cost.

Original comment by smd7...@gmail.com on 24 Mar 2011 at 8:36

GoogleCodeExporter commented 9 years ago 
I think we should try going towards the furthest blob from the main blob as one 
of the comments proposed.  Also, "if you can flood all remaining squares of a 
color this is a free move."  Something to keep in mind for sure.

Original comment by smd7...@gmail.com on 24 Mar 2011 at 8:44

GoogleCodeExporter commented 9 years ago 
ok. and i take that back about the bottom-right node. we should instead find 
the node that will take longest to get to. Perhaps? I seem to be confused as to 
how to get A* to work with the current game we are using (im watching the 
tutorial now).

Original comment by drdaniel...@gmail.com on 24 Mar 2011 at 8:44

GoogleCodeExporter commented 9 years ago 
Watching that video too.  Very helpful.

Original comment by smd7...@gmail.com on 24 Mar 2011 at 8:55

GoogleCodeExporter commented 9 years ago 
and i reuploaded the source code from the video (its in C# so pretty similar) 
so you dont have to wait for the dl time: 
http://www.mediafire.com/?p7rr2g5e822ks0p

Original comment by drdaniel...@gmail.com on 24 Mar 2011 at 8:55

GoogleCodeExporter commented 9 years ago 
I watched part 1 of the video and I can't really see the practical purpose of 
A* for the case study. It seems like if we just used this to get from the top 
left to the bottom right corner, we'd just be re-doing the same thing Mike Z 
did except much less efficiently.

I'm sure it would be applicable since you guys are pursuing it... please 
enlighten me.

Original comment by joeaar...@gmail.com on 24 Mar 2011 at 10:37

GoogleCodeExporter commented 9 years ago 
sorry we're still working on that but the basic idea is explained in post 1 
here (sorry it hasnt been posted): 
http://stackoverflow.com/questions/1430962/how-to-optimally-solve-the-flood-fill
-puzzle

However, I'm thinking only to test the bottom row of blocks for the paths.

Original comment by drdaniel...@gmail.com on 24 Mar 2011 at 11:36

GoogleCodeExporter commented 9 years ago 
i stumbled upon this i will read it tomorrow: http://arxiv.org/abs/1001.4420 
(go download pdf)

Original comment by drdaniel...@gmail.com on 24 Mar 2011 at 11:38

GoogleCodeExporter commented 9 years ago 
Best A* psuedo-code ive seen http://wiki.gamegardens.com/Path_Finding_Tutorial

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 12:15

GoogleCodeExporter commented 9 years ago 
http://www.google.com/url?sa=t&source=web&cd=18&ved=0CEwQFjAHOAo&url=http%3A%2F%
2Fpeople.maths.ox.ac.uk%2Fscott%2FPapers%2Ffloodit.pdf&rct=j&q=flood%20it%20game
s%20algorithm&ei=qd-LTY7mJIW40QHshbmtCw&usg=AFQjCNHvEgnLhYkGjndA_nqTZ7LjNRgR5A&c
ad=rja

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 12:21

GoogleCodeExporter commented 9 years ago 
http://people.maths.ox.ac.uk/scott/Papers/floodit.pdf

better link. also, polynomial time isn't so good.

Original comment by sreservoir on 25 Mar 2011 at 12:22

GoogleCodeExporter commented 9 years ago 
we can't possibly do better than polynomial...

Original comment by smd7...@gmail.com on 25 Mar 2011 at 12:57

GoogleCodeExporter commented 9 years ago 
that's polynomial on side length, yes? in that case, we might not strictly do 
better, but we can get a pretty low coefficient on that quadratic term with 
diag+A*.

Original comment by sreservoir on 25 Mar 2011 at 12:59

GoogleCodeExporter commented 9 years ago 
Yes I think its polynomial on graph size and colors. we can't possibly beat 
polynomial for this problem but the key is going to be to get those 
coefficients low. those articles only provide methods of finding the least 
number of moves, correct. I think we should definitely check that out so we 
know how far we are from optimal but I don't think it provides an actual 
solution. A* does look promising but won't the diagonal method overestimate the 
cost since there's bound to be a better path? We can't overestimate at all or 
else A* breaks.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 1:16

GoogleCodeExporter commented 9 years ago 
find the largest blob and divide the Manhattan distance by that size. We would 
be guaranteed to be under it.

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 1:21

GoogleCodeExporter commented 9 years ago

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 1:26

GoogleCodeExporter commented 9 years ago 
Maybe best blob for distance rather than largest because largest can just be a 
horizontal line. Also, this still doesn't guarantee it won't overestimate. Just 
makes it unlikely. There could be a quick path around the edges that the 
diagonal method misses.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 1:29

GoogleCodeExporter commented 9 years ago 
the horizontal-line blob is probably the best-case blob, because it has maximum 
perimeter. count best blob by perimeter instead of size, and it should be fine.

Original comment by sreservoir on 25 Mar 2011 at 1:37

GoogleCodeExporter commented 9 years ago 
I'm not exactly sure how A* works but that horizontal line blob wouldn't 
necessarily be used because of its size. All we're looking for now is the most 
accurate, non-overestimating method of determining the cost to go from point a 
to point b. Actual benefit of individual moves is irrelevant.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 1:42

GoogleCodeExporter commented 9 years ago 
dude. hang on. that could be a new way to judge moves! perimeter gained.
Anyway, how would it be possible for my algorithm to over-estimate?

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 1:54

GoogleCodeExporter commented 9 years ago 
That idea has already been proposed but I agree that we should go forward with 
the implementation of it. Also, imagine a puzzle where there's just a line 
traveling around the perimeter puzzle but skips the top left corner, so the 
diagonal solver ignores it. we could still overestimate the cost in a puzzle 
like that.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 1:59

GoogleCodeExporter commented 9 years ago 
... I've been telling you that perimeter is strategically the second most 
important thing you can do, and you haven't gotten to it until now?

@26 diagonal actually won't skip that unless the middle of the puzzle is 
pathological, simply because any change also affects everything else the blob 
touches as a side-effect. this is kind of the point.

I mean, sure, you can make a pathological board, but I suspect that the tests 
will be normal, randomly generated.

Original comment by sreservoir on 25 Mar 2011 at 2:10

GoogleCodeExporter commented 9 years ago 
Agreed, just using that example to prove the point that we can't quite 
guarantee that a cost isn't an overestimate while using that method.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 2:14

GoogleCodeExporter commented 9 years ago 
dude then when u divide the diagonal size by the size of that blob ud get ~1. 
which is correct.

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 2:15

GoogleCodeExporter commented 9 years ago 
What?

Original comment by smd7...@gmail.com on 25 Mar 2011 at 2:18

GoogleCodeExporter commented 9 years ago 
indeed. and you /want/ that blob, because it's basically the best case of blob, 
so not to use it would be a bad thing.

Original comment by sreservoir on 25 Mar 2011 at 2:27

GoogleCodeExporter commented 9 years ago 
I thought that said negative one...sorry.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 11:48

GoogleCodeExporter commented 9 years ago 
incidentally, why are we using a* instead of standard dijkstra? a* is just 
dijkstra with extra complications to find a "good enough" solution instead of 
the "best" solution, so dijkstra would actually probably be easier to implement.

Original comment by sreservoir on 25 Mar 2011 at 6:47

GoogleCodeExporter commented 9 years ago 
Dijkstra's algorithm might not perform as well as the A* search algorithm but I 
agree that we should first implement that to get the hang of this new method of 
solving.  Should the distance value just be 1, or should it be inversely 
proportional to the "value" of the blob (size, perimeter, etc...) so that we're 
more likely to follow high-reward paths?

Original comment by smd7...@gmail.com on 25 Mar 2011 at 8:16

GoogleCodeExporter commented 9 years ago 
I'd say use lowest distance of surrounding spaces, plus one iff different 
color, and account for that in addition to the value of its blob.

Original comment by sreservoir on 25 Mar 2011 at 9:18

GoogleCodeExporter commented 9 years ago 
i think we should have a method which finds the value of the spot, and that way 
we can just return 1 if we want to change.

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 9:19

GoogleCodeExporter commented 9 years ago 
I just committed what I did so far.  I followed Wikipedia's Dijkstra code and 
then printed out what the blob grid looks like afterwards (with distances, and 
previous nodes).

Original comment by smd7...@gmail.com on 25 Mar 2011 at 9:25

GoogleCodeExporter commented 9 years ago 
@35 I don't exactly understand what you're saying.  All surrounding spaces 
would be a distance of one, correct?  Also, if we used blobs, that would 
automatically account for an adjacent space being a different color.
@36 I also don't really understand what you're saying.  All of these graph 
search algorithms go through all or most of the nodes to find the shortest 
path.  It wouldn't make sense to find the value of each individual spot with 
some method.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 9:29

GoogleCodeExporter commented 9 years ago 
as I understand it, you're storing the each grid with a pair (distance,location 
from)?

Original comment by sreservoir on 25 Mar 2011 at 9:29

GoogleCodeExporter commented 9 years ago 
@39 Each blob has it's normal attributes stored, such as color and size.  Also, 
I've added in distance, which is distance from the root blob, and previous, 
which is the previous blob in a reverse path to the root blob.  The root blob's 
distance is 0 and previous is null.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 9:32

GoogleCodeExporter commented 9 years ago 
okay, I haven't actually read through your auxiliaries, but they have 
ridiculous overhead. any chance of getting that to a usable amount?

Original comment by sreservoir on 25 Mar 2011 at 9:36

GoogleCodeExporter commented 9 years ago 
Right now, I'm going to make it so we use the shortest path to the furthest 
blob, and repeat until the puzzle is solved.  This, in theory, should be better 
than DiagonalSolver move-wise, albeit not as fast.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 9:37

GoogleCodeExporter commented 9 years ago 
@38 I was reffering to comment 34 in which you said that it should be 
"inversely proportional"

@40 are you using diagonal or manhattan distance (or other)?

Also, my weekend is basically trashed so sorry that I won't be getting much 
done :-/

Original comment by drdaniel...@gmail.com on 25 Mar 2011 at 9:37

GoogleCodeExporter commented 9 years ago 
@41 Right now I'm just trying to get this to work correctly.  We can work on 
optimization afterwards, just as we did for BruteForceSolver.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 9:38

GoogleCodeExporter commented 9 years ago 
@43 Neither, really.  If I wrote it correctly, it should be the number of moves 
needed to reach the particular blob from the root blob.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 9:40

GoogleCodeExporter commented 9 years ago 
@41 However, if you find any reasonably simple optimizations, feel free to add 
them in.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 9:43

GoogleCodeExporter commented 9 years ago 
@42 that's not really much of an accomplishment, considering DiagonalSolver is 
made purely to execute ridiculously fast and yet still manage a decent number 
of moves.

@45 keep in mind, if you're counting number of moves from root blob, then 
you'll have to recompute every single time, and it would probably be better 
simply to use a reverse-linked list with end at the root blob, then simply 
count the number of blobs traversed. but then we'd need a boolean to say "part 
of root node."

Original comment by sreservoir on 25 Mar 2011 at 9:52

GoogleCodeExporter commented 9 years ago 
I finished Djikstra's and it's pretty fast and pretty good with moves (71 moves 
for 50x50 in 1.5s).  I noticed something weird is happening though.  I get 
different results when I use performMove(move) than I do when I recreate the 
grid each time.  This leads me to believe that performMove is doing something 
wrong and we need to figure out what that is.

Original comment by smd7...@gmail.com on 25 Mar 2011 at 11:39

GoogleCodeExporter commented 9 years ago 
effected minor optimization by removing unnecessary use of ArrayList, and 
kluged performMove() to make it seem to work so we can deal with what's 
actually borked, which is changeColor(). once we do that, it should run faster 
(order of half as much time, before profiling + optimization), because then we 
won't have to regenerate the board all the time.

Original comment by sreservoir on 26 Mar 2011 at 12:41

GoogleCodeExporter commented 9 years ago 
can you rewrite getBlobs(ArrayList<Blob>,Blob) into either unrolled-recursive 
with its own stack, or something non-recursive altogether? as it is, it crashes 
with stack overflow on 100.

Original comment by sreservoir on 26 Mar 2011 at 12:48