Cellular automaton logic bug

[Jbard]

Hi

I haven't posted here for a while as I haven't been using flash, just got back into it and I am struggling with logic bug I have had for days now.

This may turn into a longish post so hopefully I explain myself correctly.

Basically I am trying to create a top down view of water. So my program creates a grid of say 5x5 cells, each cell is 50px wide.

The problem I am having is in the update function. Basically each cell has 3 possible states. empty -> new -> source.

empty is what everything starts off as, then in the update statement we loop through every cell. If that cell is next to a source cell then it becomes 'new', and one cycle of being new it becomes a source cell.

Once a cell is a source it has a _level variable between 0 - 5. If it is next to a source cell more than it's current _level then it increases.

Anyway I have some sort of issue were some cells aren't being detected as 'source' cells although they are. I will include the update function below but you will get a better idea by downloading my files. I have commented out all the other directional checks apart form the top and bottom to highlight the problem. Basically the wave should be the same on each side but you can see the bottom travels quicker

public function update(e:Event = null):void{
            
            //UPDATE NEW TO SOURCE
            for(var g:int = 0; g < _horCount; g++){
                                        
                for(var h:int = 0; h < _verCount; h++){
                        
                    var _cellN:Cell = _cells[g][h];
                        
                    if(_cellN._state == 'new'){
                        trace('new set to source');
                        _cellN.setState('source');
                            
                    }
                }
            }
            
            trace('sources updated');
            
            var _cell:Cell;
            
            
            
            for(var i:int = 0; i< _horCount; i++){
                
                
                for(var j:int = 0; j<_verCount; j++){
                    
                    _cell = _cells[i][j];
                    
                
                    //CHECK NORTH
                    if(j > 0){
                        
                        if (_cells[i][j-1]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i][j-1]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i][j-1]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                continue;
                            }
                            
                        }
                    }
                    
                    //CHECK SOUTH
                    if ( j < _maxHeight ){
                        
                        if (_cells[i][j+1]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i][j+1]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i][j+1]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                continue;
                            }
                            
                        }
                    }
                    
                                        
                    
                    //CHECK EAST
                    if ( i < _maxWidth ){
                        
                        if (_cells[i+1][j]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i+1][j]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i+1][j]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                continue;
                            }
                            
                        }
                    }
                    
                    //CHECK SOUTH EAST
                    if ( i < _maxWidth && j < _maxHeight ){
                        
                        if (_cells[i+1][j+1]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i+1][j+1]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i+1][j+1]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                
                                continue;
                            }
                            
                        }
                    }
                    
                    
                    //CHECK NORTH WEST
                    if ( i > 0 && j > 0 ){
                        
                        if (_cells[i-1][j-1]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i-1][j-1]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i-1][j-1]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                continue;
                            }
                            
                        }
                    }
                    //CHECK NORTH EAST
                    if(i < _maxWidth && j > 0){
                        
                        if (_cells[i+1][j-1]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i+1][j-1]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i+1][j-1]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                continue;
                            }
                            
                        }
                        
                    }
                    
                    
                    
                    //CHECK SOUTH WEST
                    if ( i > 0 && j < _maxHeight ){
                        
                        if (_cells[i-1][j+1]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i-1][j+1]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i-1][j+1]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                continue;
                            }
                        }
                            
                    }
                    
                    
                    
                    
                    //CHECK WEST
                    if ( i > 0 ){
                        
                        if (_cells[i-1][j]._state == 'source'){
                            
                            if(_cell._state == 'source' && _cell._level < _cells[i-1][j]._level && _cell._level < 5){
                                _cell.increaseLevel();
                                continue;
                            }else if(_cell._level != 5 && _cell._level != _cells[i-1][j]._level && _cell._state != 'source'){
                                _cell.setState('new');
                                continue;
                            }
                        }
                    }
                    
                    
                    
                    //END OF CHECKS
                                    
                }
                    
            }
        
            
            
            
        } 

I would really appreciate any help.

Cheers

[5TonsOfFlax]

You are doing the new->source loop, then the source checking loop. If a cell goes from new to source, it will be evaluated as a source in the next part. Similarly, each of your directional check parts can set the cell back to new before rest of the directions are checked.

[Jbard]

Thanks for you reply.

You are doing the new->source loop, then the source checking loop. If a cell goes from new to source, it will be evaluated as a source in the next part.

Yes that is the intended effect. All 'empty' blocks that should be set to 'new' and set in the second loop, then on the next call of .update() these new blocks are set to 'source' blocks.

Similarly, each of your directional check parts can set the cell back to new before rest of the directions are checked.

As far as I can see (and I just did some extra checking to be sure) if a block is set from new-> source it can never go back to new again.

Either way I don't think this is part of my problem. In testing I have removed the whole concept of a 'new' block, so they go straight from empty->source and I still get the issue that the bottom blocks increase levels faster than the top blocks.

Also as another note in testing I found that i get the same error if I reverse the loop, so if I start the loop at the bottom right block and work backwards (instead of currently starting at top left block) the error is the same just reversed. So top blocks work as expected but bottom blocks are a step behind.

[5TonsOfFlax]

I hadn't looked closely, it seems you do have a "is not source" clause in each of the ifs that lead to setNew.

Anyway, rather than manipulating your grid in-place, I think you'll find an easier time of it by using a secondary grid. Go through one grid, setting states in the other grid. Then swap the two to render. Or just swap which one you're passing to the rendering code.

[Jbard]

I hadn't looked closely, it seems you do have a "is not source" clause in each of the ifs that lead to setNew.

Anyway, rather than manipulating your grid in-place, I think you'll find an easier time of it by using a secondary grid. Go through one grid, setting states in the other grid. Then swap the two to render. Or just swap which one you're passing to the rendering code.

A couple of updates, I have rewritten the update function to push source blocks out instead of pulling source blocks in(not sure if that make sense). It is working fine now, I originally went with pull as read a few blocks that said this used less resources but I will stick with push for now.

I have attached my code but pretty keen to investigate this idea of 2 grids. Can you explain why this will help me?

[5TonsOfFlax]

The idea behind using two grids is that you do not change the grid while calculating the next state. If you don't use two grids, then as you evaluate and set each cell's new state, the neighboring cells that depend on it which you haven't got to yet will have to use the cell's new state rather than old state to calculate their new state. Doing this means that a single time tick does not affect the entire grid at once, as you probably want it to. Instead, it washes over the grid in the order you process cells. This leads to weird bugs like you found where some cells behave as expected, and other cells appear to get odd data.
It's the usual implementation strategy for conway's game of life.
http://en.wikipedia.org/wiki/Conway'...ife#Algorithms

Most of the early algorithms were similar; they represented Life patterns as two-dimensional arrays in computer memory. Typically two arrays are used, one to hold the current generation, and one in which to calculate its successor.