Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Fri Apr 18, 2014 2:06 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 4 posts ] 
Author Message
 Post subject: Walkabout on android
PostPosted: Tue Jun 07, 2011 9:50 am 
Offline
User avatar

Joined: Fri Feb 06, 2009 2:57 pm
Location: Pittsburgh
I downloaded a game on android called Walkabout. You walk along a grid, and every block you step on falls out from under you and some blocks MUST BE STEPPED ON (have a star to collect)

This got me started on wondering what's the best way to computationally solve these levels? There is a level where every block that can be stepped on must be stepped on.

I don't know how I'd apply rules to a solution, but I know the levels could be bruteforced.

I would put together an interpreter to parse handmade level codes (something like _ for spot you can step on, * for a star to collect, and # for an obstacle, o for starting position) and then have the program identify any locations from the start that are like this:
Code:
####
##*#
____
because you cannot get out from that location, it would have to be the last star you collect.

The level that got me thinking about this would be layed out like this:
Code:
* * * * * # # # * * * *
* # * * * * * * * * * *
* * * * # * * * # * * #
# * * * # * # * * * * *
* * * * * * * * # * * *
* * * # * * * * # * * *
* # * * * * * o * * * *
* * * # * * * # * * # #


I can't figure this out, but if you go anyway other than right from the start, I don't know how you could get back there to finish up those stars. I've gotten all but one star once.

Anyone want to give input on how someone would make a solver for levels like that (that could even possibly recognize impossible levels like this one)
Code:
# * * * #
O * * * #
# * * * #


Aww heck, I'll make a quick java applet version of it maybe, without graphics most likely, in the next couple of days. I think the easiest thing to do would almost be a maze generator kind of thing.

Code:
# # # # #
# o|* * #
# *|*|* #
# * *|* #
# # # # #

_________________
3x3x3 PB: 00:48.10
"Study gravitation, it's a field with a lot of potential."
Image


Last edited by theVDude on Tue Jun 07, 2011 11:21 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Walkabout on android
PostPosted: Tue Jun 07, 2011 11:13 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Well the naive algorithm would be depth-first search which I would probably implement via recursion. I suspect the runtime will be too high to be useful on the large levels though.

If there were no obstacles a Hilbert Space Filling Curve would solve every puzzle: http://en.m.wikipedia.org/wiki/Hilbert_curve

With obstacles I would examine options like A* (http://en.m.wikipedia.org/wiki/A*_search_algorithm) or variations. You'll probably have to run the algorithm from one required space to the next and then use backtracking (use recursion) to find the proper order you should visit the goal tiles.

It might be that the levels are small enough and your computer fast enough that you can tolerate runtimes such as O(N^3).

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Walkabout on android
PostPosted: Tue Jun 07, 2011 11:26 am 
Offline
User avatar

Joined: Fri Feb 08, 2008 1:47 am
Location: near Utrecht, Netherlands
Very interesting. I think the best way to represent these levels would be to use graphs, where each vertex can only be visited once (and consequently, you can only visit each edge at most one time). Solving a puzzle where all stepping plates are starred would be equivalent to finding a Hamiltionian Path.
Finding a Hamiltonian Path is NP-complete, so there is no known efficient solution. I think the same is true if not all plates are starred (an argument for this is that it is possible to design a level where all plates but one are starred, and you're forced to step on the one that is not starred by the geometry of the level) so it's unlikely that there's a solution more efficient than brute-forcing.

_________________
Tom's Shapeways Puzzle Shop - your order from my shop includes free stickers!
Tom's Puzzle Website


Buy my mass produced puzzles at Mefferts:
- 4x4x6 Cuboid for just $38
- Curvy Copter for just $18
- 3x4x5 Cuboid for just $34


Top
 Profile  
 
 Post subject: Re: Walkabout on android
PostPosted: Tue Jun 07, 2011 1:03 pm 
Offline
User avatar

Joined: Wed Jan 28, 2009 7:55 pm
Location: Montana
This puzzle was introduced in Pokemon Ruby and Sapphire versions before it became a standalone mini-game. Off topic detail.

What is on topic is that a maze solving algorithm may be used for this style puzzle. Tug left the whole time, where if it can go left, turn left. If not, then go straight. If it can't do either of those, go right. If it can't move, it's either at the start or at the end. If not at the end, then automatically throw stating that it's impossible.

Else, if there's a place where it can make a right, then double left, then a right again and return back to its path, do that. If there is an obstacle, put a holder in the path and tug right until it returns to the holder.

This should solve possible mazes. I'm not sure of its efficiency though because it would have to be recursive to find the end, then recursively recurse the path searching for possible forks.

_________________
Andreas Nortmann wrote:
Things like this are illegal.
If not I will pass an appropriate law.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 4 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Google Adsense [Bot], MSNbot Media and 5 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group