Simple Weighted Random Walk with Hysteresis

I've already written a solution for this, but it doesn't feel "right", so I'd like some input from others.

The rules are:

• Movement is on a 2D grid (Directions arbitrari开发者_如何学运维ly labelled N, NE, E, SE, S, SW, W, NW)
• Probabilities of moving in a given direction are relative to the direction of travel (i.e. 40% represents ahead), and weighted:

[14%][40%][14%]

[ 8%][ 4%][ 8%]

[ 4%][ 4%][ 4%]

This means with overwhelming probability, travel will continue along its current trajectory. The middle value represents stopping. As an example, if the last move was NW, then the absolute probabilities would read:

[40%][14%][ 8%]

[14%][ 4%][ 4%]

[ 8%][ 4%][ 4%]

• The probabilities are approximate - one thing I toyed with was making stopped a static 5% chance outside of the main calculation, which would have altered the probability of any other operation ever so slightly.

My current algorithm is as follows (in simplified pseudocode):

int[] probabilities = [4,40,14,8,4,4,4,8,14]

if move.previous == null:
    move.previous = STOPPED

if move.previous != STOPPED:
    // Cycle probabilities[1:8] array until indexof(move.previous) = 40%

r = Random % 99

if r < probabilities.sum[0:0]:
    move.current = STOPPED
elif r < probabilities.sum[0:1]:
    move.current = NW
elif r < probabilities.sum[0:2]:
    move.current = NW
...

Reasons why I really dislike this method:

* It forces me to assign specific roles to array indices: [0] = stopped, [1] = North...

* It forces me to operate on a subset of the array when cycling (i.e. STOPPED always remains in place)

* It's very iterative, and therefore, slow. It has to check every value in turn until it gets to the right one. Cycling the array requires up to 4 operations.

* A 9-case if-block (most languages do not allow dynamic switches).

* Stopped has to be special cased in everything.

Things I have considered:

* Circular linked list: Simplifies the cycling (make the pivot always equal north) but requires maintaining a set of pointers, and still involves assigning roles to specific indices.

* Vectors: Really not sure how I'd go about weighting this, plus I'd need to worry about magnitude.

* Matrices: Rotating matrices does not work like that :)

* Use a well-known random walk algorithm: Overkill? Though recommendations are considered. * Trees: Just thought of this, so no real thought given to it...

So. Does anyone have any bright ideas?

8You have 8 directions and when you hit some direction you have to "rotate this matrix"

But this is just modulo over finite field.

Since you have only 100 integers to pick probability from, you can just putt all integers in list and value from each integers points to index of your direction.

This direction you rotate (modulo addition) in way that it points to move that you have to make.

And than you have one array that have difference that you have to apply to your move.

somethihing like that.

                   40 numbers    14 numbers   8 numbers
 int[100] probab={0,0,0,0,0,0,....,1,1,1,.......,2,2,2,...};

and then

                    N      NE    E     SE       STOP   
int[9] next_move={{0,1},{ 1,1},{1,1},{1,-1}...,{0,0}}; //in circle

So you pick

move=probab[randint(100)]

if(move != 8)//if 8 you got stop
{
   move=(prevous_move+move)%8;
}

move_x=next_move[move][0];
move_y=next_move[move][1];

Use a more direct representation of direction in your algorithms, something like a (dx, dy) pair, for example. This allows you to move by just having x += dx; y += dy; (You can still use the "direction ENUM" + a lookup table if you wish...)

Your next problem is finding a good representation of the "probability table". Since r only ranges from 1 to 99 it might be feasible to just do a dumb array and use prob_table[r] directly.

Then, compute a 3x3 matrix of these probability tables using the method of your choice. It doesn't matter if it is slow because you only do it once.

To get the next direction simply

prob_table = dir_table[curr_dx][curr_dy];
(curr_dx, curr_dy) = get_next_dir(prob_table, random_number());