[Haskell-beginners] High precision doubles

Aaron MacDonald aaronjm at eastlink.ca
Wed Jun 24 22:10:45 EDT 2009


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.


More information about the Beginners mailing list