[Haskell-beginners] High precision doubles

[Matthew Eastman]

This is a coincidence. I just finished writing a hexagonal (and  
square) maze generator.

I used Wilson's algorithm, which builds a spanning tree by performing  
a random walk from each cell not in the maze until it reaches a cell  
that is in the maze. It then adds the path and goes at it again until  
every cell is in the maze.

If you're using a grid, even one without bounds, it makes sense to use  
integer coordinates and map them to floating point when you need to,  
like some others have suggested.

The grid I used looked something like this:
      ___     ___
  ___/   \___/   \___
/   \___/   \___/   \
\___/2,2\___/   \___/
/1,2\___/3,2\___/   \
\___/2,1\___/   \___/
/1,1\___/3,1\___/   \
\___/   \___/   \___/

It would work with negative numbers as well, if you need the grid to  
be able to expand in every direction.

You move north, south, east, or west by adding to or subtracting from  
the x and y co-ordinates.
If the x coordinate is even, you add 1 to y when you move north-east  
or north-west.
If the x coordinate is odd, you subtract 1 from y when you move south- 
east or south-west.

Then when you're testing whether a cell is in your maze you just need  
to check the (x,y) integer pair and not have to worry about floating  
point precision, and you can get all the cells adjacent to a specific  
cell by adding to and subtracting from the x or y value of a cell.

I found it easier to keep track of which walls each cell has instead  
of which cells it's adjacent to, but either one works.

Just for fun, one of the mazes it made:

      ___     ___     ___     ___     ___
  ___/   \___/   \___/   \___/   \___/   \___
/   \       \   /       /       /   \       \
\       \___/    ___/    ___/       /   \   /
/   \___/    ___    \       \___/   \   /   \
\   /   \___/   \   /   \   /   \___    \   /
/       /    ___/   \___/    ___    \___/   \
\___/       /   \___    \___/   \___    \   /
/   \   /            ___     ___/   \___/   \
\___    \___/   \       \   /            ___/
/    ___    \___/   \___/   \___/   \___    \
\___/   \___/   \___/   \___/   \___/   \___/

On 24-Jun-09, at 10:10 PM, Aaron MacDonald wrote:

>
> On 24-Jun-09, at 10:18 PM, Andrew Hunter wrote:
>> More to the point, however: you don't want more precision.  Welcome  
>> to
>> the world of numerical algorithms; floating point arithmetic is
>> inherently inexact.  Get used to it.  For example, I'll bet your
>> errors are caused by testing for equality against zero, and if I had
>> to guess, you're probably trying to terminate a procedure when some
>> value hits zero?  It's not going to; you need to introduce the  
>> concept
>> of tolerances, and accept if |val| < tol.  This is a simplistic
>> solution and not really right in most cases, but might help.  If you
>> want more advice about how to handle floating-point inaccuracy, could
>> you provide a program and what's going wrong?
>
> What I'm specifically working on is a maze generator.  The generator  
> is based on Prim's algorithm: starting with a graph containing a  
> single node, I connect new nodes to existing nodes that are not  
> surrounded yet until I've reached a specified number of nodes in the  
> graph.
>
> In my case, the maze is on a hexagonal grid.  There are no  
> boundaries around the maze, so the generator may attach hexagonal  
> cells, or nodes, from any side (I don't particularly care if the  
> generator sometimes makes one long hallway).  Each hexagonal cell is  
> represented in the graph as a co-ordinate representing the cell's  
> centre.  I have a function that takes a co-ordinate and returns a  
> list of co-ordinates representing the centres of the adjacent cells.  
> Keeping track of the hexagons' positions is important because these  
> mazes will be levels for a game I hope to somehow put together; the  
> potions would be used for drawing the maze and for AI pathfinding.
>
> When adding a new node/hex to the graph/maze, I pick an existing  
> node and get all of its neighbour co-ordinates, filtering out co- 
> ordinates that represent nodes already present in the graph. The  
> problem is that, due to floating point errors, these co-ordinates  
> are not be exact. If hex A has the co-ordinate for hex B in its list  
> of adjacent hexes, hex B would not necessarily have the co-ordinate  
> for hex A in its own list. Things get mismatched quickly.
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners