Simple weighted random walk with hysteresis

Question

I already wrote a solution for this, but it does not feel “right”, so I would like to receive information from others.

Rules:

• The movement is on a 2D grid (Directions arbitrarily indicated by N, NE, E, SE, S, SW, W, NW)
• The probabilities of movement in a given direction relate to the direction of movement (i.e. 40% represent forward) and are weighted:

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

This means that with overwhelming probability the movement will continue along the current trajectory. The average value means stop. As an example, if the last step was NW, then the absolute probabilities would read:

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

• Probabilities are approximate - one thing I played with was that I stopped the 5% static probability outside the basic calculation, which would slightly change the probability of any other operation.

My current algorithm is as follows (in a 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 don't like this method:
* This forces me to assign specific roles to the array indices: [0] = stopped, [1] = North ...
* This forces me to work with a subset of the array when looping (i.e. STOPPED always stays in place)
* It is very iterative, and therefore slow. It should check each value in turn until it hits the correct one. An array requires up to 4 operations.
* 9-case if-block (most languages ​​do not allow dynamic switches).
* Stopped should be a special cover in everything.

Things I reviewed:
* Cyclic linked list: simplifies cycling (makes the axis always equal to the north), but requires support for a set of pointers and still includes assigning roles to specific indexes.
* Vectors: Not really sure how I would do this, plus I need to worry about the size.
* Matrices: Rotating matrices do not work like this:

* Use the famous random walk algorithm: Overkill? Although recommendations are being considered. * Trees: Just thought about it, so no real thought was given to him ...

So. Anyone have any bright ideas?

Answer 1

8 You have 8 directions, and when you get in some direction, you need to “rotate this matrix”

But this is just modulo over a finite field.

Since you only have 100 integers to choose a probability, you can simply drop all the integers in the list and the value from each integer to the index of your direction.

In this direction, you rotate (modulo addition) so that it indicates the movement you must make.

And than you have one array that has a difference that you must apply to your movement.

something like.

  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 choose

 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]; 

Answer 2

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

Your next problem is to find a good representation of the "probability table". Since r can only be from 1 to 99, it is possible to just make a dumb array and use prob_table[r] directly.

Then calculate the 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 just

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