Reputation: 4816
I am trying to write my own Game of Life, with my own set of rules. First 'concept', which I would like to apply, is socialization (which basicaly means if the cell wants to be alone or in a group with other cells). Data structure is 2-dimensional array (for now).
In order to be able to move a cell to/away from a group of another cells, I need to determine where to move it. The idea is, that I evaluate all the cells in the area (neighbours) and get a vector, which tells me where to move the cell. Size of the vector is 0 or 1 (don't move or move) and the angle is array of directions (up, down, right, left).
This is a image with representation of forces to a cell, like I imagined it (but reach could be more than 5):
Let's for example take this picture:
Forces from lower left neighbour: down (0), up (2), right (2), left (0)
Forces from right neighbour : down (0), up (0), right (0), left (2)
sum : down (0), up (2), right (0), left (0)
So the cell should go up.
I could write an algorithm with a lot of if statements and check all cells in the neighbourhood. Of course this algorithm would be easiest if the 'reach' parameter is set to 1 (first column on picture 1). But what if I change reach parameter to 10 for example? I would need to write an algorithm for each 'reach' parameter in advance... How can I avoid this (notice, that the force is growing potentialy (1, 2, 4, 8, 16, 32,...))? Can I use specific design pattern for this problem?
Also: the most important thing is not speed, but to be able to extend initial logic.
Things to take into consideration:
Upvotes: 13
Views: 453
Reputation: 4996
It should not be difficult to write your algorithm to search all of the cells within the reach distance of a particular cell C
. Each cell that has an inhabitant would have a particular force of repulsion on cell C
. This force of repulsion is based on the distance from the cell to cell C
. In the example that you have given, that force of repulsion is based upon the L-1 distance and is 2^(reach-distance)
. Each repulsion force is then added together to create a cumulative force that dictates the direction in which to move the inhabitant in cell C
.
You do not need to write an algorithm for each different reach. The magnitude of the force can be determined via a simple formula. If you change that formula to something else such as a Fibonacci number, you should still be able to calculate the magnitude as needed based upon the distance and the reach.
Here is some rough code written in pseudo-Java showing the basic ideas: http://codepad.org/K6zxnOAx
enum Direction {Left, Right, Up, Down, None};
Direction push(boolean board[][], int testX, int testY, int reach)
{
int xWeight = 0;
int yWeight = 0;
for (int xDist=-reach; xDist<=+reach; ++xDist)
{
for (int yDist=-reach; yDist<=+reach; ++yDist)
{
int normDist = abs(xDist) + abs(yDist);
if (0<normDist && normDist<reach)
{
int x = testX + xDist;
int y = testY + yDist;
if (0<=x && x<board.length && 0<=y && y<board[0].length)
{
if (board[x][y])
{
int force = getForceMagnitude(reach, normDist);
xWeight += sign(xDist) * force;
yWeight += sign(yDist) * force;
}
}
}
}
}
if (xWeight==0 && yWeight==0) return Direction.None;
if (abs(xWeight) > abs(yWeight))
{
return xWeight<0 ? Direction.Left : Direction.Right;
}
else
{
return yWeight<0 ? Direction.Up : Direction.Down;
}
}
int getForceMagnitude(int reach, int distance)
{
return 1<<(reach-distance);
}
Upvotes: 4
Reputation: 49156
Write a function to loop over the neighbors:
:
def CalculateForceOnCell(x, y):
force_on_x_y = [0,0,0,0]
for i in range(max(0, x-reach), min(WIDTH, x+reach)+1):
limited_reach = reach - abs(x-i)
for j in range(max(0, y - limited_reach), min(HEIGHT, y + limited_reach + 1)):
force_coefficient = limited_reach + 1
AddNeighborForce(force_on_x_y, (x, y), (i, j), force_coefficient)
return force_on_x_y
Upvotes: 0