Re: Path algorithm

[Nick Collier]

Hi,

If you can model the grid2d as a network of cells (nodes) where the 
links connect wet nodes to other wet nodes and / or safe nodes, you 
should then be able to use the usual graph algorithms, depth-first etc 
to traverse the network appropriately. The actual algorithm to use will 
depend on what your network characteristics (cyclic, directed, etc.) 
are. Any algorithms books should have a chapter or two on graph 
algorithms. Sedgewick's _Algorithms in C++_ has nearly 100 pages.

Creating the network won't be hard to code. Just iterate over the cells 
creating nodes and links where appropriate. This will slow down your 
model though. Of course, your grid may not be tractable as a network due 
to size or complexity constraints, and so this whole thing may be out 
the window. As I recall your grid is enormous, but if your fish are 
fairly close together you could perhaps get away with making a network 
from only the cells near the fish at that time.

Nick

M Lang / S Railsback wrote:

> I need an algorithm to see if you can get from one place in a Grid2D to
> another region of the grid.
>
> Say there are a patch of connected grid cells that are "safe" for my
> fish. The other cells are either wet or dry, and the fish can only move
> through wet cells. I need to determine for each wet cell whether or not
> there is a connection through the other wet cells to the "safe" patch.
>
> Does anyone have an efficient algorithm for this? 
>
> Thanks
>
> Steve



                 ==================================
  Swarm-Modelling is for discussion of Simulation and Modelling techniques
  esp. using Swarm.  For list administration needs (esp. [un]subscribing),
  please send a message to <address@hidden> with "help" in the
  body of the message.
                 ==================================