How would you approach this...

Discussion in 'Computer Science & Culture' started by adaptiveView, Feb 4, 2003.

Thread Status:
Not open for further replies.
  1. adaptiveView Registered Member

    Messages:
    14

    Please Register or Log in to view the hidden image!



    How would you approach generating valid (solvable) games of the type shown above?

    The rules are:

    1) The tractor may move forward or backward.
    2) The tractor can only negotiate turns around "cut corners" (it can't turn a "red corner").
    3) The tractor cannot back up into the ball.

    The goal is to push the ball out of the "maze" (i.e., back to where the tractor is currently sitting).

    I'd like to programmatically generate different configurations of this game (same layout, different "cut corners") that are solvable and to order them according to difficulty (e.g., so if you solve a game, the next game is more difficult).

    I am wondering if anyone here can suggest a methodology for this (or provide a URL to something discussing an approach that might work).

    Thanks in advance!
     
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Persol I am the great and mighty Zo. Registered Senior Member

    Messages:
    5,946
    Considering today's proccessing power, I'd suggest a randomly generated 'map'. Then have the computer try and solve it (variation on maze pathing). The difficulty would be equivalent to the number of steps the computer took (not perfect, but ok).
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. NanoTec Registered Senior Member

    Messages:
    30
    Corner – three options: forward, forward-backward-turn, turn
    To test create a linked list –lightcone- of every possible combination until the robot tractor can move no more or encounters the ball. To reduce the processing time generate possible paths from both the entrance and target and see where they intersect as n^2 +n^2 + 2n < (2n)^2. Sorry for the terse post.

    Generate a number of random maps and just have the software check every one.
    Can the tractor back over the ball then move foreword to pick it up?
    The grater the number of possibilities and/or turns the more difficulty the player will have. Possibly rank the players according to if they found the shortest path.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. adaptiveView Registered Member

    Messages:
    14
    Corner: 4 options - (1) forward past corner (except when at a corner of the "game board"), (2) reverse past corner (except when at a corner of the "game board"), (3) turn, and (4) change direction (except when at a corner of the "game board"), e.g., if going forward, turn and then go in reverse, heading in a different direction than you came from.

    No, the tractor can't back over the ball.

    The game has a few subtleties that make mapping out possible paths more difficult. In the config shown above, for example, you can't navigate to the ball and then directly to the exit. You have to move the ball into a new position and then back out and come at it from a different direction in order to get the ball out.

    Thanks for the ideas; good food for thought...
     
  8. NanoTec Registered Senior Member

    Messages:
    30
    Sorry… I am realizing that what I wrote didn’t help.

    EAS Exit accessibility subroutine: ball must be pushed out – from what points can this occur if the tractor has the ball.

    TAS Tractor accessibility subroutine: where can the tractor get to without the ball blocking its path. (Lookup table with checking for ball position)

    GB Get Ball: What are the TAS maps that go to the ball with the tractor pointing in the proper direction.

    PTAS Pushing Tractor accessibility subroutine – where can it take the ball without reversing; record every point for which there is an alternate facing GB

    ECC Exit Checking Code – does the PTAS intersect the EAS.
     
Thread Status:
Not open for further replies.

Share This Page