Jump to content
Aaron

A Puzzle Game

Recommended Posts

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. :)

Share this post


Link to post
Share on other sites

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. 8)

 

 

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
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.

 

:)

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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.

Share this post


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

898684[/snapback]

 

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).

Share this post


Link to post
Share on other sites
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.

898626[/snapback]

I'm interested :)

Share this post


Link to post
Share on other sites
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.

898626[/snapback]

I'm interested :)

898833[/snapback]

 

Me too! :cool:

Share this post


Link to post
Share on other sites
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! :evil:

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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.

 

:)

898677[/snapback]

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......

 

 

 

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.

899433[/snapback]

 

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). :roll:

 

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

 

 

 

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! :evil:

899018[/snapback]

 

Easily, you say? :ponder:

Share this post


Link to post
Share on other sites
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.

 

Easily, you say?  :ponder:

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.

Share this post


Link to post
Share on other sites
If you are talking about MS Visual C++, you are right. It is outdated and buggy. Go to www.stlport.org.

901311[/snapback]

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... :roll:

 

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.

 

 

 

Easily, you say?  :ponder:

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...

astar_30Jul05.zip

Share this post


Link to post
Share on other sites

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.

astar_30Oct05.zip

Share this post


Link to post
Share on other sites
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.

956901[/snapback]

 

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

Share this post


Link to post
Share on other sites

This is very cool. :D 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?

Share this post


Link to post
Share on other sites
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?

957086[/snapback]

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

 

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...

Share this post


Link to post
Share on other sites

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. ;)

Share this post


Link to post
Share on other sites

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. :roll:

 

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...

asgen.zip

Share this post


Link to post
Share on other sites

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 :roll:

 

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...

astar_6Feb06.zip

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

I just discovered this game. It is a really good puzzle game. I have been looking around trying to figure out how many levels it has but I have not found anything except the programmer said he had 18 levels completed at one time. Does anyone know how many levels the finished game has in it?

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...