[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Path algorithm
From: |
Nick Collier |
Subject: |
Re: Path algorithm |
Date: |
Tue, 06 Mar 2001 09:26:30 -0600 |
User-agent: |
Mozilla/5.0 (X11; U; Linux 2.2.14-5.0 i686; en-US; 0.8) Gecko/20010215 |
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.
==================================