-----------------------------------

Cervantes

Thu Jul 28, 2005 3:43 pm


Odd Even Path Puzzle Solver

-----------------------------------

In the attachment are four files (two normal files, two module units).  If you want to play OE Path, run "OE Path Play.t".  If you want to (sort of) solve a puzzle, run "OE Path Solve.t".  

The puzzle works like this: You pick a place on the grid to start at, then move from piece to piece in a path trying to get the highest score possible.  You can only move immediately above, below, right, or left of you.  No diagonal moves are allowed.  If you start on an even number, you can only travel on pieces that have even numbers.  Similarly, if you start on an odd number you can only travel on pieces that host an odd number.


This puzzle is more interesting to solve.  I haven't quite done it, actually.  So far I've made it so that the user picks the starting location.  From there, the program will find the best possible path.

To improve this, I'm currently thinking that the user should pick a point on the path that (s)he thinks will be the best in the level.  Then the program would search out the best and second best paths with the piece that was picked by the user as the starting position.  The two paths would then be joined.  Note that something would have to be done to prevent the best and second best paths from overlapping.

Next, the user shouldn't have to pick where to start.  The program should automatically scan the level and find the place to start the search at.  This would be the most difficult part of the program, I think.  My ideas for this are limited to grouping the grid into compartments of odd and even patches.  Then, a spot in the compartment with the largest total score would be chosen and the searching begins.  This would not, however, take into account the fact that not all pieces in a compartment can be reached (ie. sometimes getting a piece means travelling into a dead end.  These pieces shouldn't be included in the compartment).

This idea of compartments could also be used to speed up the current program.  Now when I say a compartment, however, I mean a section of the same type (odd or even) that does not go into a bottleneck.  Often times in this game you'll go from one large, open section of, say, evens, through a narrow path, into another wider area.  Instead of searching every possible pattern, we should find the best path through the first open area (what I referred to as a compartment at the beginning of this paragraph) that will lead to the bottleneck.  Then we take the bottleneck to the second compartment and finish it.

Lastly, I'm aware of some bugs, such as you cannot exit the program.  Pff, that's not a primary concern!  Just click the 'x'. :)  Also, the solver doesn't tell you the current score.  Easily fixed, though I don't want to re-zip it.

Anyone have any suggestions as to how to further develop this program, or how to optimize the current program?
Thanks!


-----------------------------------

zylum

Thu Jul 28, 2005 5:51 pm



-----------------------------------

again plain recursion with a slight optimization... i loop through each square of the grid and start my path there.. once the path is finished then each consecutive path cannot travel on the first space of any preceding path. this makes my algorithm speed up as it progresses.

setscreen ("offscreenonly,graphics:500;500,nobuttonbar")

const N := 12
const gridSize := maxx div (N + 2)
var grid : array 1 .. N, 1 .. N of int
var travelled : array 0 .. N + 1, 0 .. N + 1 of boolean
var font : int := Font.New ("Arial:14")
var score : int := 0

type Coords :
    record
        x : int
        y : int
    end record

var path : flexible array 1 .. 0 of Coords
var bestPath : flexible array 1 .. 0 of Coords
var bestScore : int := 0

proc drawGrid
    locate (1, 1)
    put "Best Score: ", bestScore, " Current Score: ", score, " Elapsed Time: ", Time.Elapsed / 1000
    for x : 1 .. N
        for y : 1 .. N
            Draw.FillBox (x * gridSize, y * gridSize, x * gridSize + gridSize, y * gridSize + gridSize, grey)
            Draw.Box (x * gridSize, y * gridSize, x * gridSize + gridSize, y * gridSize + gridSize, black)
            Draw.Text (intstr (grid (x, y)), x * gridSize + gridSize div 2 - Font.Width (intstr (grid (x, y)), font) div 2,
                y * gridSize + gridSize div 2 - gridSize div 5, font, (grid (x, y) mod 2) * black)
        end for
    end for
    if upper (bestPath) > 1 then
        for i : 2 .. upper (bestPath)
            Draw.ThickLine (bestPath (i - 1).x * gridSize + gridSize div 2, bestPath (i - 1).y * gridSize + gridSize div 2,
                bestPath (i).x * gridSize + gridSize div 2, bestPath (i).y * gridSize + gridSize div 2, 5, green)
        end for
    end if
    if upper (path) > 1 then
        for i : 2 .. upper (path)
            Draw.ThickLine (path (i - 1).x * gridSize + gridSize div 2, path (i - 1).y * gridSize + gridSize div 2,
                path (i).x * gridSize + gridSize div 2, path (i).y * gridSize + gridSize div 2, 2, brightred)
        end for
    end if
    View.Update
end drawGrid

proc fillGrid
    for x : 0 .. N + 1
        for y : 0 .. N + 1
            if x > 0 and x  0 and y  bestScore then
            bestScore := cs
            new bestPath, upper (path)
            for i : 1 .. upper (path)
                bestPath (i).x := path (i).x
                bestPath (i).y := path (i).y
            end for
        end if
        return
    end if
    new path, upper (path) + 1
    path (upper (path)).x := x
    path (upper (path)).y := y
    %/*