Blank Spaces assigned weights

a456df (17)
Having trouble figuring out how make part of this game. I'm currently trying to assign value (weight) to blank spaces in a program. The values need to decrease as they move toward a 'L' (land) spaces. There are 'W' spaces to indicate water that is too deep to travel through. These are set to 2000000. The L is set to 0. The blank spaces are initialized with -1. The point is to get a 'P' (person) to a land space. I want the player to start on a space farthest from land and race against the computer to get to a land space first without going into the water that is too deep to travel through. I'm using a 2d array.

//Initialize weight values

void WaterGame::initWeights()
{
// Allocate the number of required rows (pointers)
weights = new int*[ height() ];

// Allocate each row
for( int i = 0; i < height(); i++ ) {
weights[i] = new int[ width() ];

//Set each cell as uninitialized
for( int j = 0; j < width(); j++ ) {
weights[i][j] = W_UNINIT;

// Set deep water space weights
if( toupper(track[i][j]) == 'W' ) {
weights[i][j] = W_WATER;
}
else if( toupper(track[i][j]) == 'L' ) {
// Set land space weight
weights[i][j] = W_LAND;
}
}
}
//This is where I'm stuck currently

}
Duthomhas (13206)
1. Use std::vector. Your life will get significantly easier.

2. You don’t necessarily need to store the same thing in the array vector that you display on screen. Your ‘display’ function (whatever you call it) should know how to translate the information you keep to what the user sees.
(Re-reading your question, I think that you are doing this...?)

3. Use a function that has a random variance. For example, assign the water depth/weight something related to its distance from the target land. Except allow the depth to be some random value more or less than the result of the function.

Good luck!
a456df (17)
Ah, you're right. My mind was going the wrong direction when I posted.
I'm very new to this and need to learn more on vectors.

Also, any ideas on a function I could use to assign something related to the distance form the land target position?
Duthomhas (13206)
For distance from a point in cartesian space, use the Pythagorean Theorem:

    x² + y² = r²

To avoid too much noise in your depths, I would use the equation, with the random noise variance, for every 5ᵗʰ cell (square), then just smooth the squares between them.

1) Generate distance based offsets with random variance in depth

    +---+---+---+---+---+---+---+---+---+
    | ❶ |   |   |   | ❶ |   |   |   | ❶ |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    | ❶ |   |   |   | ❶ |   |   |   | ❶ |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    | ❶ |   |   |   | ❶ |   |   |   | ❶ |
    +---+---+---+---+---+---+---+---+---+

2) Find depth between each of those points and apply a proportionally smaller random variance

    +---+---+---+---+---+---+---+---+---+
    | ① |   | ❷ |   | ① |   | ❷ |   | ① |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    | ❷ |   | ❷ |   | ❷ |   | ❷ |   | ❷ |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    | ① |   | ❷ |   | ① |   | ❷ |   | ① |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    | ❷ |   | ❷ |   | ❷ |   | ❷ |   | ❷ |
    +---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+
    | ① |   | ❷ |   | ① |   | ❷ |   | ① |
    +---+---+---+---+---+---+---+---+---+

3) Repeat to finish the entire block

    +---+---+---+---+---+---+---+---+---+
    | ① | ❸ | ② | ❸ | ① | ❸ | ② | ❸ | ① |
    +---+---+---+---+---+---+---+---+---+
    | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ |
    +---+---+---+---+---+---+---+---+---+
    | ② | ❸ | ② | ❸ | ② | ❸ | ② | ❸ | ② |
    +---+---+---+---+---+---+---+---+---+
    | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ |
    +---+---+---+---+---+---+---+---+---+
    | ① | ❸ | ② | ❸ | ① | ❸ | ② | ❸ | ① |
    +---+---+---+---+---+---+---+---+---+
    | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ |
    +---+---+---+---+---+---+---+---+---+
    | ② | ❸ | ② | ❸ | ② | ❸ | ② | ❸ | ② |
    +---+---+---+---+---+---+---+---+---+
    | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ | ❸ |
    +---+---+---+---+---+---+---+---+---+
    | ① | ❸ | ② | ❸ | ① | ❸ | ② | ❸ | ① |
    +---+---+---+---+---+---+---+---+---+

Of course you will have obstacles (land?) dotting your map, so not every square will be ocean to fill with a depth. Etc.

[edit] Dang browser/website puts extra space between each line of text, ruining my pretty graphic...

[edit 2] Hopefully that's better...
Last edited on
mbozzi (3932)
It's a path-finding problem, needs a graph algorithm.

See:
https://en.wikipedia.org/wiki/Dijkstra's_algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
#include <queue>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cassert>
#include <limits>

constexpr int width = 10;
constexpr int height = 10;
constexpr int unset_distance = std::numeric_limits<int>::max();
constexpr int shallow_water_cost = 1;
constexpr int deep_water_cost = 12;

struct tile
{
  bool impassable;
  bool aground;
  
  int distance;
};

struct edge
{
  int x;
  int y;
  
  int distance;
};

static constexpr auto operator<=>(edge a, edge b) { return a.distance <=> b.distance; }

#define _ tile{ .impassable = false, .aground = false, .distance = unset_distance }
#define W tile{ .impassable = true,  .aground = false, .distance = unset_distance }
#define L tile{ .impassable = true,  .aground = true,  .distance = unset_distance }
tile board[width * height]
{
  _, _, L, L, L, L, _, _, _, _,
  _, _, _, L, L, _, _, _, _, _,
  _, _, _, _, _, _, _, _, _, _,
  _, W, W, W, _, _, _, _, _, _,
  _, W, W, W, _, _, W, W, _, _,
  _, _, W, _, _, L, L, L, L, _,
  _, _, _, _, L, L, L, _, L, _,
  _, _, _, _, _, L, L, L, L, _,
  _, _, _, _, _, _, L, L, _, _,
  _, _, _, _, _, _, _, _, _, _,
}; 
#undef L
#undef W
#undef _

[[nodiscard]] static constexpr bool in_bounds_x(int x) { return x >= 0 && x < width; }
[[nodiscard]] static constexpr bool in_bounds_y(int y) { return y >= 0 && y < height; }
[[nodiscard]] static constexpr bool in_bounds(int x, int y) { return in_bounds_x(x) && in_bounds_y(y); }

[[nodiscard]] static constexpr int xy(int x, int y)
{
  assert(in_bounds_x(x));
  assert(in_bounds_y(y));

  return x + y * width;
}

using queue_type = std::priority_queue<edge, std::vector<edge>, std::greater<edge>>;

static void push_coastal_tiles_onto_queue(int x, int y, queue_type& queue)
{
  if (in_bounds(x, y))
  {
    if (tile& v = board[xy(x, y)]; v.distance == unset_distance)
    {
      if (v.aground)
      {
        v.distance = 0;
        push_coastal_tiles_onto_queue(x + 1, y, queue);
        push_coastal_tiles_onto_queue(x - 1, y, queue);
        push_coastal_tiles_onto_queue(x, y + 1, queue);
        push_coastal_tiles_onto_queue(x, y - 1, queue);
      }
      else queue.push({x, y, v.impassable? deep_water_cost: shallow_water_cost});
    }
  }
}

int main()
{
  queue_type queue;

  for (int y = 0; y < height; ++y)
  {
    for (int x = 0; x < width; ++x)
      if (tile& v = board[xy(x, y)]; v.aground && v.distance == unset_distance)
        push_coastal_tiles_onto_queue(x, y, queue);
  }

  while (queue.size())
  {
    auto [x, y, d] = queue.top(); queue.pop();

    if (tile& v = board[xy(x, y)]; v.distance > d)
    {
      v.distance = d;
      if (in_bounds(x - 1, y)) queue.push({x - 1, y, d + (board[xy(x - 1, y)].impassable? deep_water_cost: shallow_water_cost)});
      if (in_bounds(x + 1, y)) queue.push({x + 1, y, d + (board[xy(x + 1, y)].impassable? deep_water_cost: shallow_water_cost)});
      if (in_bounds(x, y + 1)) queue.push({x, y + 1, d + (board[xy(x, y + 1)].impassable? deep_water_cost: shallow_water_cost)});
      if (in_bounds(x, y - 1)) queue.push({x, y - 1, d + (board[xy(x, y - 1)].impassable? deep_water_cost: shallow_water_cost)});
    }
  }

  for (int y = 0; y < height; ++y)
  {
    for (int x = 0; x < width; ++x)
      std::cout << std::setw(2) << (board[xy(x, y)].distance) << ' ';
    std::cout << '\n';
  }
}


Live demo:
https://godbolt.org/z/b4PYs5bq6

The output is 
 2  1  0  0  0  0  1  2  3  4 
 3  2  1  0  0  1  2  3  4  5 
 4  3  2  1  1  2  3  4  3  4 
 5 15 14 13  2  2  3  3  2  3 
 6 16 26 14  2  1 12 12  1  2 
 5  4 14  2  1  0  0  0  0  1 
 4  3  2  1  0  0  0  1  0  1 
 5  4  3  2  1  0  0  0  0  1 
 6  5  4  3  2  1  0  0  1  2 
 7  6  5  4  3  2  1  1  2  3
Last edited on
a456df (17)
HUGE help! Thank you!
mbozzi (3932)
Whoops, I did some extra work in the above:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
// Find the "minimum distance to land" in a grid-based map consisting of land
// and water tiles.

#include <queue>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cassert>
#include <limits>

constexpr int width = 10;
constexpr int height = 10;
constexpr int unset_distance = std::numeric_limits<int>::max();
constexpr int shallow_water_cost = 1;
constexpr int deep_water_cost = 12;

struct tile
{
  bool impassable;
  bool aground;
  
  int distance;
};

struct edge
{
  int x;
  int y;
  
  int distance;
};

static constexpr auto operator<=>(edge a, edge b) { return a.distance <=> b.distance; }

#define _ tile{ .impassable = false, .aground = false, .distance = unset_distance }
#define W tile{ .impassable = true,  .aground = false, .distance = unset_distance }
#define L tile{ .impassable = true,  .aground = true,  .distance = unset_distance }
tile board[width * height]
{
  _, _, L, L, L, L, _, _, _, _,
  _, _, _, L, L, _, _, _, _, _,
  _, _, _, _, _, _, _, _, _, _,
  _, W, W, W, _, _, _, _, _, _,
  _, W, W, W, _, _, W, W, _, _,
  _, _, W, _, _, L, L, L, L, _,
  _, _, _, _, L, L, L, _, L, _,
  _, _, _, _, _, L, L, L, L, _,
  _, _, _, _, _, _, L, L, _, _,
  _, _, _, _, _, _, _, _, _, _,
}; 
#undef L
#undef W
#undef _

[[nodiscard]] static constexpr bool in_bounds_x(int x) { return x >= 0 && x < width; }
[[nodiscard]] static constexpr bool in_bounds_y(int y) { return y >= 0 && y < height; }
[[nodiscard]] static constexpr bool in_bounds(int x, int y) { return in_bounds_x(x) && in_bounds_y(y); }

[[nodiscard]] static constexpr int xy(int x, int y)
{
  assert(in_bounds_x(x));
  assert(in_bounds_y(y));

  return x + y * width;
}

using queue_type = std::priority_queue<edge, std::vector<edge>, std::greater<edge>>;

int main()
{
  queue_type queue;

  for (int y = 0; y < height; ++y)
  {
    for (int x = 0; x < width; ++x)
      if (tile& v = board[xy(x, y)]; v.aground && v.distance == unset_distance)
        queue.push({x, y, 0});
  }

  while (queue.size())
  {
    auto [x, y, d] = queue.top(); queue.pop();

    if (tile& v = board[xy(x, y)]; v.distance > d)
    {
      v.distance = d;
      if (in_bounds(x - 1, y)) queue.push({x - 1, y, d + (board[xy(x - 1, y)].impassable? deep_water_cost: shallow_water_cost)});
      if (in_bounds(x + 1, y)) queue.push({x + 1, y, d + (board[xy(x + 1, y)].impassable? deep_water_cost: shallow_water_cost)});
      if (in_bounds(x, y + 1)) queue.push({x, y + 1, d + (board[xy(x, y + 1)].impassable? deep_water_cost: shallow_water_cost)});
      if (in_bounds(x, y - 1)) queue.push({x, y - 1, d + (board[xy(x, y - 1)].impassable? deep_water_cost: shallow_water_cost)});
    }
  }

  for (int y = 0; y < height; ++y)
  {
    for (int x = 0; x < width; ++x)
      std::cout << std::setw(2) << (board[xy(x, y)].distance) << ' ';
    std::cout << '\n';
  }
}


https://godbolt.org/z/8c7xehWev
Topic archived. No new replies allowed.