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.

You won't be able to get it working easily with floating-point numbers. Ideally, you would use integers for the code you're describing, then scale them to the proper floating-point values later.

I am reading this and still don't understand what is the question. You should never operate two floating point numbers expecting to result zero. Period. Floating point numbers are intrinsically imprecise. Every time you write an interactive process with floating points in the exit conditions, you should use some tolerance, either relative or absolute. Absolute exit condition: abs (xnew - xold) < epsilon Relative exit condition (valid only when dealing with non-zero values) abs ((xold+xnew)/xnew) wrote:

Am Donnerstag 25 Juni 2009 04:14:19 schrieb Sean Bartell:

...

...

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.

You won't be able to get it working easily with floating-point numbers. Ideally, you would use integers for the code you're describing, then scale them to the proper floating-point values later.

Say the hexagons have side length 2, the centre of one is at (0,0) and one of its vertices at (2,0). Then the centre of any hexagon has coordinates (3*k,m*sqrt 3), for some integers k, m and any vertex has coordinates (i,j*sqrt 3) for integers i, j. So in this case, he could work with floating point values; using a large tolerance, he could build a gigantic grid before having false results.

But of course, it is much better to use (k,m), resp. (i,j), as coordinates and translate that to floating point only for drawing. _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

-- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

G'day all. Quoting Rafael Gustavo da Cunha Pereira Pinto :

I am reading this and still don't understand what is the question. You should never operate two floating point numbers expecting to result zero. Period.

WARNING: Advanced material follows. A 32-bit integer fits losslessly in the mantissa of a Double. Any of the basic integer operations which work correctly on 32-bit integers must also work correctly when that integer is stored in a Double. You are allowed to assume this. Cheers, Andrew Bromage

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@haskell.org http://www.haskell.org/mailman/listinfo/beginners

Sure, I can put it on Hackage. I'll have to figure out how to use Cabal, and tidy up the code, but I'll upload it sooner or later. On 28-Jun-09, at 10:55 PM, Felipe Lessa wrote:

On Sun, Jun 28, 2009 at 10:34:51PM -0400, Matthew Eastman wrote:

...

Just for fun, one of the mazes it made:

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

This is beautiful! Do you plan releasing something to Hackage?

-- Felipe. _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners