- May 2, 2019
- 32
- 24
Some fun coding stuff here:
I thought a little bit about how to implement a nice battle combat map system, and came up with a good solution. Should simplify pathfinding in battle terrain, at the expense of some cache locality.
When you allocate a buffer of cells, interleave each cell with an unreachable one like so:
Then traversals become super simple. If our current position is {row = 3, column = 2},
Checking edges is also simple, just check for out of dimension bounds for the buffer. If a traversal is pushing us past the total internal column count or the total internal row count (or below zero for both), that move can't be made.
EDIT: The distance calculations below are wrong. I'll leave this in as an example of poor sample data picking.
EDIT: The issue is that stepping vertically, going down+left and down+right will take one step with this calculation.
To calculate the distance from a cell to another cell, you subtract the "coordinates" of those two cells, absolute value both components, sum them and divide by 2, will give the distance.
EDIT: Here is the correct calculation. A little more complex than expected, but fine anyway.
We first count the number of rows we traveled, and if this number is smaller than the number of columns traveled, add half of the difference between column steps and row steps to our count.
I thought a little bit about how to implement a nice battle combat map system, and came up with a good solution. Should simplify pathfinding in battle terrain, at the expense of some cache locality.
When you allocate a buffer of cells, interleave each cell with an unreachable one like so:
Code:
[ ][cell][ ][cell][ ][cell][ ][from]
[cell][ ][cell][ ][cell][ ][cell][ ]
[ ][cell][ ][3, 2][ ][cell][ ][cell]
[cell][ ][cell][ ][cell][ ][cell][ ]
[ ][ to ][ ][cell][ ][cell][ ][to#2]Then traversals become super simple. If our current position is {row = 3, column = 2},
- move right -> {row, column + 2}
- move left -> {row, column - 2}
- move up and right -> {row - 1, column + 1}
- move up and left -> {row - 1, column - 1}
- move down and right -> {row + 1, column + 1}
- move down and left -> {row + 1, column - 1}
Checking edges is also simple, just check for out of dimension bounds for the buffer. If a traversal is pushing us past the total internal column count or the total internal row count (or below zero for both), that move can't be made.
EDIT: The distance calculations below are wrong. I'll leave this in as an example of poor sample data picking.
EDIT: The issue is that stepping vertically, going down+left and down+right will take one step with this calculation.
To calculate the distance from a cell to another cell, you subtract the "coordinates" of those two cells, absolute value both components, sum them and divide by 2, will give the distance.
Code:
from = {0, 7}
to = {4, 1}
sub = {4 - 0, 1 - 7} = {4, -6}
abs = |{4, -6}| = {4, 6}
sum = 4 + 6 = 10
div = 10/2 = 5We first count the number of rows we traveled, and if this number is smaller than the number of columns traveled, add half of the difference between column steps and row steps to our count.
Code:
from = {0, 7}
to = {4, 1}
count := 0
sub = {4 - 0, 1 - 7} = {4, -6}
abs = |{4, -6}| = {4, 6}
count := 4
if [4 < 6] -> true
count += (6 - 4)/2 = 1
-------------------------
count : 5
Code:
from = {0, 7}
to#2 = {4, 7}
count := 0
sub = {4 - 0, 7 - 7} = {4, 0}
abs = |{4, 0}| = {4, 0}
count := 4
if [4 < 0] -> false
done
-------------------------
count : 4
Last edited:
