48 replies to this topic

[Zach]

Although A* will be faster, a brute force complete search will be simplest to program. Since you only have to solve each puzzle once, it may not be that bad.

You might even be able to recruit computing time from fellow AA'ers.

[vdub_bobby]

Good job with this so far. I'll second Al's thought that the 2600 needs more puzzle games!

[Zach]

I just realized, because the movable objects advance until they bump a obstacle, there will always be less than 4 moves per object.* So really you are dealing will 6^n branches. Furthermore, objects will only have 2 moves most of the time. The brute-force search is looking better.


* Yes, there is a possible exception for the first move.

[Aaron]

All good points.

I read up on A* a little more (saw a guy using it to solve a 15-puzzle) and there still seems to be one problem - it requires some idea of closeness to the solution. The most obvious thing I guess is to count the number of rings left remaining, but this has problems since there's a lot of set-up work involved in getting them. Also I've deliberately made some of the levels so that collecting the closest ring will screw you up.

But anyway... checking for duplicate states would help a lot, since there are "only" about 10 million different possibilities. Maybe a lot less actually. So now I guess I'll just have to write something and see if it works...


Lastly... can I get an interest check on level contributions? I'm more than happy to create them all myself, but if people would actually want to do such a thing, I could maybe cook up an editor.

[Thomas Jentzsch]

Aaron, on Tue Jul 26, 2005 7:35 AM, said:

I read up on A* a little more (saw a guy using it to solve a 15-puzzle) and there still seems to be one problem - it requires some idea of closeness to the solution.

Since you have to calculate to the end anyway, why not simply using the number of moves for A*? (slow, but 100% correct)

[Zach]

Aaron, on Tue Jul 26, 2005 12:35 AM, said:

All good points.

I read up on A* a little more (saw a guy using it to solve a 15-puzzle) and there still seems to be one problem - it requires some idea of closeness to the solution.

Hey Aaron,

I solved a similar 8 puzzle using A* as a homework assignment once. You are correct about needing an "idea of closeness", but this needs some more explanation.

An A* search consists of calculating two values; I'll call them g and h, where g is the cost incurred so far, and h is an estimate of the remaining cost to get to the goal. In the example of a maze, the cost refers to the distance traveled, and in your application the cost would be the number of moves.

The heuristic, h, has a specific requirement: it must never overestimate the remaining cost - this is needed to guarantee the optimal solution. In finding a path through a maze, h is usually the linear distance between the current point the the goal. Obviously this is an underestimate because the distance traveled between two points can not be less than the linear distance. The safest heuristic is to let h=0, which is what I believe Thomas suggested. Clearly it will always underestimate how many step are left, but usually it will be far from the true amount. The trick to speeding up your A* is to find a "smarter" h.

So to sum up, we should try to think of a way to estimate how many moves are left at each point, without going over. If there are no better ideas, we can always use h=0.

[djmips]

I haven't used A* myself but from what I understand setting h=0 is equivalent to Dijkstra's algorithm. Is this correct?

[Zach]

Quote

The most obvious thing I guess is to count the number of rings left remaining, but this has problems since there's a lot of set-up work involved in getting them. Also I've deliberately made some of the levels so that collecting the closest ring will screw you up.

By the way, counting the rings remaining will be an effective heuristic, as long as you don't have a scenario where you can pick up two rings with a single move. To assume it will always take 1 or more moves to get each ring is a good underestimate. The set-up work involved in getting the rings will be sorted out by the search. If you grab a ring early on and screw yourself up, the search will eventually reach a point where g grows too high, and the search will switch to another path.

[Zach]

djmips, on Tue Jul 26, 2005 3:56 AM, said:

I haven't used A* myself but from what I understand setting h=0 is equivalent to Dijkstra's algorithm. Is this correct?

I believe so. In the case of Aaron's puzzle, Dijkstra's algorithm is also equivalent to a regular brute force search, since each move costs the same amount (1 step).

[vdub_bobby]

Aaron, on Mon Jul 25, 2005 10:35 PM, said:

Lastly...  can I get an interest check on level contributions?  I'm more than happy to create them all myself, but if people would actually want to do such a thing, I could maybe cook up an editor.

I'm interested

[Gateway]

vdub_bobby, on Tue Jul 26, 2005 9:28 AM, said:

Aaron, on Mon Jul 25, 2005 10:35 PM, said:

Lastly...  can I get an interest check on level contributions?  I'm more than happy to create them all myself, but if people would actually want to do such a thing, I could maybe cook up an editor.

I'm interested

Me too!

[Thomas Jentzsch]

Aaron, on Tue Jul 26, 2005 7:35 AM, said:

Lastly...  can I get an interest check on level contributions?  I'm more than happy to create them all myself, but if people would actually want to do such a thing, I could maybe cook up an editor.

Once you have a program which finds optimal solutions for a given level, you easily modify it to create levels.

Especially levels which are really nasty!

[Zach]

Aaron, if you're still interested in A*, here's an idea for a better heuristic. If a ring is not in the same row or column as Non-Infringing-Yellow-Pie-Shaped-Man, he will need at least two moves to get to it. So all you do is take the number of those rings, double, and add the number of any rings that are in the same row/column*. That gives you a safe lower bound for the number of remaining moves.

If you want to get more sophisticated, if a ring is in the same row/column as the player but an obstacle is in between, it will take at least 3 moves to catch it.


*If two or more rings are in the same row/column and in the same direction, they should only count as one.

[Aaron]

Zach, on Tue Jul 26, 2005 3:01 AM, said:

Hey Aaron,

I solved a similar 8 puzzle using A* as a homework assignment once. You are correct about needing an "idea of closeness", but this needs some more explanation.

An A* search consists of calculating  two values; I'll call them g and h, where g is the cost incurred so far, and h is an estimate of the remaining cost to get to the goal. In the example of a maze, the cost refers to the distance traveled, and in your application the cost would be the number of moves.

The heuristic, h, has a specific requirement: it must never overestimate the remaining cost - this is needed to guarantee the optimal solution.  In finding a path through a maze, h is usually the linear distance between the current point the the goal. Obviously this is an underestimate because the distance traveled between two points can not be less than the linear distance. The safest heuristic is to let  h=0, which is what I believe Thomas suggested. Clearly it will always underestimate how many step are left, but usually it will be far from the true amount. The trick to speeding up your A* is to find a "smarter" h.

So to sum up, we should try to think of a way to estimate how many moves are left at each point, without going over. If there are no better ideas, we can always use  h=0.

I understand all that just fine, what I was referring to (not clearly, I guess) was the difficulty in creating an effective and useful "h" value. With the "path" to the solution being as convoluted as it is, even using a very accurate estimate of h, it'll stilll take a long time to reach a solution.

Anyway, I've discovered I don't have quite enough computing power to go with h=0, so......

Zach, on Wed Jul 27, 2005 3:35 AM, said:

Aaron, if you're still interested in A*, here's an idea for a better heuristic. If a ring is not in the same row or column as Non-Infringing-Yellow-Pie-Shaped-Man, he will need at least two moves to get to it. So all you do is take the number of those rings, double, and add the number of any rings that are in the same row/column*.  That gives you a safe lower bound for the number of remaining moves.

If you want to get more sophisticated, if a ring is in the same row/column as the player but an obstacle is in between, it will take at least 3 moves to catch it.


*If two or more rings are in the same row/column and in the same direction, they should only count as one.

I did go with something sort-of similar to what you suggested:
min(# of occupied rows, # of occupied columns) * 2 - 1
...since you can potentially clear all the rings in any row/column in two moves, except for the one you're currently in, which only takes one.

Even so, it still takes me all day to run the thing, so I don't have the solutions yet (I screwed up the first try).

A bit OT - afaik C++ STL doesn't have a hash table, can anyone point me towards a good one?

Thomas Jentzsch, on Tue Jul 26, 2005 2:12 PM, said:

Once you have a program which finds optimal solutions for a given level, you easily modify it to create levels.

Especially levels which are really nasty!

Easily, you say?

[Thomas Jentzsch]

Aaron, on Sat Jul 30, 2005 8:54 AM, said:

A bit OT - afaik C++ STL doesn't have a hash table, can anyone point me towards a good one?

If you are talking about MS Visual C++, you are right. It is outdated and buggy. Go to www.stlport.org.

Quote

Easily, you say? 

Yup. Just design a level (or let a generator generate or modify it) and let the programm run reverse until it finds the position which is most far away.

[Aaron]

Thomas Jentzsch, on Sat Jul 30, 2005 2:29 AM, said:

If you are talking about MS Visual C++, you are right. It is outdated and buggy. Go to www.stlport.org.

I'm using MinGW, but I had no idea that stuff existed. Thanks!

Although I must say, it was an incredible headache to get working. The syntax for creating a hashing function is freakin' strange, to say the least. And I still don't have everything installed correctly...

But anyway... the important parts work, and my solution-finder runs much faster for it - all four puzzles done in under an hour (3&4 actually were under a minute).

So here's a minor update to the game. The score will change color once you pass the minimum number of moves, plus the left difficulty switch works as an undo.

Quote

Quote

Easily, you say? 

Yup. Just design a level (or let a generator generate or modify it) and let the programm run reverse until it finds the position which is most far away.

Clever. I was thinking you meant computer-generate the level from scratch...

Attached Files

•  astar_30Jul05.zip   1.61K   147 downloads

[Aaron]

Time to dredge up an old topic!

I haven't had much time to work on this (or really do much of anything) for the past couple months, but I did manage to get some stuff done today, just in time for the compo. New in this version:

music & sound effects
new pickup graphics
cool fade effects
title screen
victory screen (if you find all the optimal solutions)
two new levels

There's room for around 30 levels (no compression ), but I don't have any kind of level editor yet, so they're not going to get made any time soon. If I do get around to writing an editor, I'll post it here for everyone to play with.

Attached Files

•  astar_30Oct05.zip   2.57K   137 downloads

[jussts]

Aaron, on Sun Oct 30, 2005 6:34 PM, said:

Time to dredge up an old topic!

I haven't had much time to work on this (or really do much of anything)  for the past couple months, but I did manage to get some stuff done today, just in time for the compo.  New in this version:

music & sound effects
new pickup graphics
cool fade effects
title screen
victory screen (if you find all the optimal solutions)
two new levels

There's room for around 30 levels (no compression ), but I don't have any kind of level editor yet, so they're not going to get made any time soon.  If I do get around to writing an editor, I'll post it here for everyone to play with.

Wow, you put some serious polish on this game... very impressive.

[Nathan Strum]

This is very cool. Fun game, and quite challenging, too. Nice graphics, too.

Pac-Man fits very well with this game, but if this goes onto a cart, won't you have to change him to something else?

[Aaron]

Nathan Strum, on Mon Oct 31, 2005 12:36 AM, said:

Pac-Man fits very well with this game, but if this goes onto a cart, won't you have to change him to something else?

Shh. No one will notice. Anyway, he's non-infringing yellow pie shaped man.

Actually, the main character of the game is really the yellow square from Adventure.

But um, yeah, I guess you're right. If it comes down to it I could just re-use the character from Fall Down or something...

[Nathan Strum]

You could just change his color and call him K.C. Munchkin.

Or maybe Casey Munchin'. Can't see how that could possibly infringe on anything.

[Aaron]

I finally got around to writing a map generator of sorts. Basically it's just my solution finder with some extra text output, so usage will seem a little strange.

What you do is draw some nice ascii art like so...

WWWWWWWWWWWWWWWW
W....o........PW
W..WW.W...Wo.o.W
W.o.......oW...W
W......o..Wo...W
WWWWW.W........W
W.B.W.W...W.o.WW
W.o.W..........W
W...o.W........W
WWWWWWWWWWWWWWWW

...and feed it to the program, which will output some assembly source (with a solution).

I still don't have it trying to find the optimal object placement or anything, but maybe I'll get to that eventually...

Attached Files

•  asgen.zip   116.17K   130 downloads

[Aaron]

It's been many long months with little to no work on things Atari, but I've been able to get back to AStar a little bit recently and make some updates. Nothing ground-breaking, but I've added some more levels (there's 18 now), which imo was the game's biggest deficiency.

It's kind of hard to judge the difficulty of the levels, but some of the new ones should be fairly hard. I know someone at the compo suggested starting off with some easier levels without the block, which is a good idea, but I just haven't gotten around to making any

Anyway, you can turn off the fade effects with the right difficulty switch, and there are now PAL versions. There's still a couple hundred bytes still left in the rom, so more features aren't really out of the question...

Attached Files

•  astar_6Feb06.zip   9.16K   153 downloads

[Albert]

You've done a great job on this thus far and it looks quite polished! I love the use of the gradient blocks and the colorful, well drawn sprites. And of course using Pac-Man and food items is perfect. You even have a nice title scree in there with some music, and various sound effects.

An interesting use for the AtariVox/MemCard would be to keep track of which levels the player has completed and somehow displaying that status as you switch through the levels. This might give people more inspiration to complete them all so they can "finish" the game.

Also, I think 18 levels might be too few, and sounds like you won't be able to add too many more without jumping to a bankswitch cart. If you're having trouble coming up with levels, maybe some type of level design contest could be in order? If you go to a bankswitch cart, you could also add some more sprites.

..Al