Zach Posted July 25, 2005 Share Posted July 25, 2005 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. Quote Link to comment Share on other sites More sharing options...
vdub_bobby Posted July 25, 2005 Share Posted July 25, 2005 Good job with this so far. I'll second Al's thought that the 2600 needs more puzzle games! Quote Link to comment Share on other sites More sharing options...
Zach Posted July 25, 2005 Share Posted July 25, 2005 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. Quote Link to comment Share on other sites More sharing options...
Aaron Posted July 26, 2005 Author Share Posted July 26, 2005 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. Quote Link to comment Share on other sites More sharing options...
Thomas Jentzsch Posted July 26, 2005 Share Posted July 26, 2005 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) Quote Link to comment Share on other sites More sharing options...
Zach Posted July 26, 2005 Share Posted July 26, 2005 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. Quote Link to comment Share on other sites More sharing options...
djmips Posted July 26, 2005 Share Posted July 26, 2005 I haven't used A* myself but from what I understand setting h=0 is equivalent to Dijkstra's algorithm. Is this correct? Quote Link to comment Share on other sites More sharing options...
Zach Posted July 26, 2005 Share Posted July 26, 2005 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. Quote Link to comment Share on other sites More sharing options...
Zach Posted July 26, 2005 Share Posted July 26, 2005 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). Quote Link to comment Share on other sites More sharing options...
vdub_bobby Posted July 26, 2005 Share Posted July 26, 2005 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 Quote Link to comment Share on other sites More sharing options...
Gateway Posted July 26, 2005 Share Posted July 26, 2005 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! Quote Link to comment Share on other sites More sharing options...
Thomas Jentzsch Posted July 26, 2005 Share Posted July 26, 2005 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! Quote Link to comment Share on other sites More sharing options...
Zach Posted July 27, 2005 Share Posted July 27, 2005 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. Quote Link to comment Share on other sites More sharing options...
Aaron Posted July 30, 2005 Author Share Posted July 30, 2005 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). 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! 899018[/snapback] Easily, you say? Quote Link to comment Share on other sites More sharing options...
Thomas Jentzsch Posted July 30, 2005 Share Posted July 30, 2005 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? 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. Quote Link to comment Share on other sites More sharing options...
Aaron Posted July 31, 2005 Author Share Posted July 31, 2005 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... 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? 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 Quote Link to comment Share on other sites More sharing options...
Aaron Posted October 30, 2005 Author Share Posted October 30, 2005 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 Quote Link to comment Share on other sites More sharing options...
jussts Posted October 31, 2005 Share Posted October 31, 2005 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. Quote Link to comment Share on other sites More sharing options...
+Nathan Strum Posted October 31, 2005 Share Posted October 31, 2005 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? Quote Link to comment Share on other sites More sharing options...
Aaron Posted October 31, 2005 Author Share Posted October 31, 2005 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. 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... Quote Link to comment Share on other sites More sharing options...
+Nathan Strum Posted October 31, 2005 Share Posted October 31, 2005 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. Quote Link to comment Share on other sites More sharing options...
Aaron Posted November 20, 2005 Author Share Posted November 20, 2005 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... asgen.zip Quote Link to comment Share on other sites More sharing options...
Aaron Posted February 6, 2006 Author Share Posted February 6, 2006 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... astar_6Feb06.zip Quote Link to comment Share on other sites More sharing options...
Albert Posted March 8, 2006 Share Posted March 8, 2006 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 Quote Link to comment Share on other sites More sharing options...
accousticguitar Posted October 19, 2018 Share Posted October 19, 2018 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? Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.