C++

Forum

 
C programming. Using uninitialized memory warning.

Mif (393)
I keep getting this warning even I initialize the memory, then I double-check the code paths to ensure no element in allNodes or closedSet is accessed before allocation. I still don't understand why the warning persists.

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
 
NODE* aStar(int startX, int startY, int goalX, int goalY)
{
	int xAxe = (GAME_RES_WIDTH / SCALE_FACTOR);
	int yAxe = (GAME_RES_HEIGHT / SCALE_FACTOR);

	MINI_HEAP openSet;
	initHeap(&openSet);

	// Dynamically allocate the arrays with error checking
	NODE*** allNodes = (NODE***)calloc(xAxe, sizeof(NODE**));

	if (allNodes == NULL) 
	{
		// Handle memory allocation failure
		return NULL;
	}

	for (int i = 0; i < xAxe; i++)
	{
		allNodes[i] = (NODE**)calloc(yAxe, sizeof(NODE*));

		if (allNodes[i] == NULL)
		{
			// Free previously allocated memory on failure
			for (int j = 0; j < i; j++)
			{
				free(allNodes[j]);
			}
			free(allNodes);
			return NULL;
		}

		// Initialize to NULL to avoid uninitialized memory usage
		for (int j = 0; j < yAxe; j++)
		{
			allNodes[i][j] = NULL;  // Explicit initialization
		}
	}

	bool** closedSet = (bool**)calloc(xAxe, sizeof(bool*));

	if (closedSet == NULL) 
	{
		// Handle memory allocation failure
		for (int i = 0; i < xAxe; i++) 
		{
			free(allNodes[i]);
		}

		free(allNodes);
		return NULL;
	}

	for (int i = 0; i < xAxe; i++)
	{
		closedSet[i] = (bool*)calloc(yAxe, sizeof(bool));

		if (closedSet[i] == NULL)
		{
			// Free previously allocated memory on failure
			for (int j = 0; j < i; j++)
			{
				free(closedSet[j]);
			}

			for (int j = 0; j < xAxe; j++)
			{
				free(allNodes[j]);
			}

			free(allNodes);
			free(closedSet);
			return NULL;
		}

		for (int j = 0; j < yAxe; j++)
		{
			closedSet[i][j] = false;
		}
	}

	NODE* start = (NODE*)malloc(sizeof(NODE));

	if (start == NULL)
	{
		// Free all dynamically allocated memory before returning
		for (int i = 0; i < xAxe; i++) 
		{
			free(allNodes[i]);
			free(closedSet[i]);
		}

		free(allNodes);
		free(closedSet);
		return NULL;
	}

	start->x = startX;
	start->y = startY;
	start->gCost = 0;
	start->hCost = manhattanDistance(startX, startY, goalX, goalY);
	start->fCost = start->gCost + start->hCost;
	start->parent = NULL;

	pushHeap(&openSet, start);
	allNodes[startX][startY] = start;

	while (!isEmpty(&openSet)) 
	{
		NODE* current = popHeap(&openSet);

		if (current->x == goalX && current->y == goalY)
		{
			// Path found, clean up and return the path
			for (int i = 0; i < xAxe; i++)
			{
				for (int j = 0; j < yAxe; j++)
				{
					if (allNodes[i][j] != NULL) 
					{
						free(allNodes[i][j]);
					}
				}

				free(allNodes[i]);
				free(closedSet[i]);
			}

			free(allNodes);
			free(closedSet);
			return current;
		}

		closedSet[current->x][current->y] = true;

		for (int k = 0; k < 4; k++)
		{
			int nx = current->x + dirX[k];
			int ny = current->y + dirY[k];

			if (!isInBounds(nx, ny) || !isWalkable(nx, ny) || closedSet[nx][ny])
			{
				continue;
			}

			int newGCost = (current->gCost + 1);
			int newHCost = manhattanDistance(nx, ny, goalX, goalY);

			// Ensure safe access by checking allNodes[nx][ny] is initialized
			if (allNodes[nx][ny] == NULL || newGCost < allNodes[nx][ny]->gCost)
			{
				NODE* neighbor = (NODE*)malloc(sizeof(NODE));

				if (neighbor == NULL)
				{
					// Free memory and return if allocation fails
					for (int i = 0; i < xAxe; i++)
					{
						for (int j = 0; j < yAxe; j++)
						{
							if (allNodes[i][j] != NULL)
							{
								free(allNodes[i][j]);
							}
						}

						free(allNodes[i]);
						free(closedSet[i]);
					}

					free(allNodes);
					free(closedSet);
					return NULL;
				}

				neighbor->x = nx;
				neighbor->y = ny;
				neighbor->gCost = newGCost;
				neighbor->hCost = newHCost;
				neighbor->fCost = newGCost + newHCost;
				neighbor->parent = current;

				if (allNodes[nx][ny] == NULL)
				{
					pushHeap(&openSet, neighbor);
					allNodes[nx][ny] = neighbor;
				}
				else
				{
					free(allNodes[nx][ny]);
					allNodes[nx][ny] = neighbor;
				}
			}
		}
	}

	// No path found, clean up
	for (int i = 0; i < xAxe; i++)
	{
		for (int j = 0; j < yAxe; j++)
		{
			if (allNodes[i][j] != NULL)
			{
				free(allNodes[i][j]);
			}
		}
		free(allNodes[i]);
		free(closedSet[i]);
	}

	free(allNodes);
	free(closedSet);

	return NULL; // No path found
}


..Any thoughts how can I solve this? Maybe is there a specific compiler optimizations or configurations that is causing this?
Please help... thank you.
Mif (393)
The warning is triggered at line 202 when I check against NULL
if(allNodes[i][j] != NULL)
Duthomhas (13206)
It could be you have just confused the compiler.

Alas, I have never played with A* and cannot intelligently comment on your implementation of the algorithm. But it does not look quite right to me — you are mixing types of things and their containers in a way that makes me nervous.

One of the main problems is all the bookkeeping you have mixed into the code that can be simplified by making a few helper functions. For example, a lot of your function could be reduced to something like:

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
 
NODE* aStar(int startX, int startY, int goalX, int goalY)
{
	int xAxe = (GAME_RES_WIDTH / SCALE_FACTOR);
	int yAxe = (GAME_RES_HEIGHT / SCALE_FACTOR);

	// These are all nodes touched or examined in the search
	NODE*** allNodes = alloc_node_array(xAxe, yAxe);
	if (!allNodes) return NULL; 

	// These are nodes that have been examined
	bool** closedSet = alloc_closed_set(xAxe, yAxe);
	if (!closedSet) goto lerror;

	// These are nodes that have yet to be examined
	MINI_HEAP openSet;
	initHeap(&openSet);

	// Add the initial node
	NODE* start = alloc_node(startX, startY, 0, manhattanDistance(startX, startY, goalX, goalY), NULL);
	if (!start) goto lerror;

	pushHeap(&openSet, start);
	allNodes[startX][startY] = start;

	// While there are nodes to be examined:
	while (!isEmpty(&openSet)) 
	{

		...

	}

lerror:
	free_closed_set(closedSet, xAxe);
	free_all_nodes(allNodes, xAxe, yAxe);
	cleanupHeap(&openSet); // (did you forget to clean up the min heap?)
	return NULL; // No path found
}

The helper functions do all the work of allocating and freeing memory. For example:

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
 
bool** free_closed_set(bool** closedSet, int xAxe)
{
	if (closedSet)
	{
		for (int x = 0;  x < xAxe;  x++)
			free(closedSet[x]);
		free(closedSet);
	}
	return NULL;
}

bool** alloc_closed_set(int xAxe, int yAxe)
{
	bool** closedSet = calloc(xAxe, sizeof(bool*));
	if (closedSet)
	{
		for (int x = 0;  x < xAxe;  x++)
		{
			closedSet[x] = calloc(yAxe, sizeof(bool));
			if (!closedSet[x])
				return free_closed_set(closedSet, xAxe);
		}
	}
	return closedSet;
}

This frees you from having to do it (over and over and over) in your A* function, thus making it much easier for you to follow what you are doing.

I see that you have not as-yet added code to properly return a path. I would personally not return the NODE type directly to the caller, since it is essentially a linked list from the goal point to the start point. Instead I would use another type, such as:

1
2
3
4
5
 
struct aStarPath
{
  int x, y;
  struct aStarPath* next;
};

This can easily be constructed by following the parent nodes back to the start to produce a linked list of (x,y) coordinates from start to goal. The upsides of this approach are:

  • You also need to provide the caller with a function to delete the returned linked list.
  • You do not need to either remove nodes from allNodes or duplicate nodes in order to return something you have not free()ed during proper cleanup. The existing cleanup methods can be used simply.

You could also just allocate and return an array of (x,y) pairs, where the last element is the goal point. The user can then just iterate through the returned array with an index and simply free() it when finished with it.

So, your function would become either one of:

  struct aStarPath * aStar(int startX, int startY, int goalX, int goalY);
  struct points * aStar(int startX, int startY, int goalX, int goalY);

Anyway, sorry I don’t have a sure answer for the actual question. Without a complete example code I can compile and mess with, I cannot answer it.

Hopefully all the other notes help you.
Mif (393)
Well first of all thank you for your answer..yeahh is quite messy the code .. Soo the main thing I need to compute is to make the A* Algorithm to work with my rpg game where all the movements are 16 pixels at time. Okay soo let's see some other code that can help you understand and finally, I personally understand why this doesn't work like it should... however I solved the warning issue, still the problem isn't resolved..

Here is some of the functions that I used in the aStar function
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
 
#define GRID_WIDTH  (GAME_RES_WIDTH / SCALE_FACTOR)
#define GRID_HEIGHT ((GAME_RES_HEIGHT - 16) / SCALE_FACTOR) // -16 because the very bottom is the UI interface that is 400 by 16 pixels

// Directions for moving up, down, left, right
const int dirX[] = { 0, 0, -1, 1 };
const int dirY[] = { -1, 1, 0, 0 };

// Define a structure for nodes in the map
typedef struct NODE {
	int x, y;
	int gCost, hCost, fCost;
	struct NODE* parent;
} NODE;

// Define the grid where true is passable and false is blocked
bool grid[GRID_HEIGHT][GRID_WIDTH];

// Define a structure for the priority queue (min-heap)
typedef struct MINI_HEAP {
	NODE* nodes[GRID_WIDTH * GRID_HEIGHT];
	int size;
} MINI_HEAP;

void initHeap(MINI_HEAP* heap) {
	heap->size = 0;
}

bool isEmpty(MINI_HEAP* heap) {
	return heap->size == 0;
}

void swap(NODE** a, NODE** b) {
	NODE* temp = *a;
	*a = *b;
	*b = temp;
}

void pushHeap(MINI_HEAP* heap, NODE* node) {
	int i = heap->size++;
	while (i > 0 && node->fCost < heap->nodes[(i - 1) / 2]->fCost) {
		heap->nodes[i] = heap->nodes[(i - 1) / 2];
		i = (i - 1) / 2;
	}
	heap->nodes[i] = node;
}

NODE* popHeap(MINI_HEAP* heap) {
	if (isEmpty(heap)) {
		return NULL;
	}
	NODE* root = heap->nodes[0];
	NODE* last = heap->nodes[--heap->size];
	int i = 0, child;
	while ((child = 2 * i + 1) < heap->size) {
		if (child + 1 < heap->size && heap->nodes[child + 1]->fCost < heap->nodes[child]->fCost) {
			child++;
		}
		if (last->fCost <= heap->nodes[child]->fCost) {
			break;
		}
		heap->nodes[i] = heap->nodes[child];
		i = child;
	}
	heap->nodes[i] = last;
	return root;
}


Other functions here:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
// Manhattan distance heuristic
int manhattanDistance(int x1, int x2, int y1, int y2) {
	return abs(x1 - x2) + abs(y1 - y2);
}

// Check if coordinates are within bounds
bool isInBounds(int x, int y) {
	return (x >= 0 && x < GRID_WIDTH&& y >= 0 && y < GRID_HEIGHT);
}

// Check if a cell is walkable
bool isWalkable(int x, int y) {
	return grid[x][y] == 1;
}


Then I reconstruct the aStar function, which I have to modify it again cause is very messy even now and needs to be more structured, but at least like this the warning is gone:

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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
NODE* aStar(int startX, int startY, int goalX, int goalY) {
	MINI_HEAP openSet;
	initHeap(&openSet);

	NODE*** allNodes = (NODE***)malloc(GRID_WIDTH * sizeof(NODE**));
	bool** closedSet = (bool**)malloc(GRID_WIDTH * sizeof(bool*));

	if (allNodes == NULL || closedSet == NULL) {
		// Handle memory allocation failure
		free(allNodes);
		free(closedSet);
		return NULL;
	}

	for (int i = 0; i < GRID_WIDTH; i++) {
		allNodes[i] = (NODE**)malloc(GRID_HEIGHT * sizeof(NODE*));
		closedSet[i] = (bool*)calloc(GRID_HEIGHT, sizeof(bool));
		if (allNodes[i] == NULL || closedSet[i] == NULL) {
			// Handle memory allocation failure
			for (int j = 0; j < i; j++) {
				free(allNodes[j]);
				free(closedSet[j]);
			}
			free(allNodes);
			free(closedSet);
			return NULL;
		}
		for (int j = 0; j < GRID_HEIGHT; j++) {
			allNodes[i][j] = NULL;
		}
	}

	NODE* start = (NODE*)malloc(sizeof(NODE));
	if (start == NULL) {
		// Free all dynamically allocated memory before returning
		for (int i = 0; i < GRID_WIDTH; i++) {
			free(allNodes[i]);
			free(closedSet[i]);
		}
		free(allNodes);
		free(closedSet);
		return NULL;
	}

	start->x = startX;
	start->y = startY;
	start->gCost = 0;
	start->hCost = manhattanDistance(startX, goalX, startY, goalY);
	start->fCost = start->gCost + start->hCost;
	start->parent = NULL;

	pushHeap(&openSet, start);
	allNodes[startX][startY] = start;

	while (!isEmpty(&openSet)) {
		NODE* current = popHeap(&openSet);

		if (current->x == goalX && current->y == goalY) {
			// Free dynamically allocated memory when path is found
			for (int i = 0; i < GRID_WIDTH; i++) {
				for (int j = 0; j < GRID_HEIGHT; j++) {
					free(allNodes[i][j]);
				}
				free(allNodes[i]);
				free(closedSet[i]);
			}
			free(allNodes);
			free(closedSet);
			return current;
		}

		closedSet[current->x][current->y] = true;

		for (int k = 0; k < 4; k++) {
			int nx = current->x + dirX[k];
			int ny = current->y + dirY[k];

			if (!isInBounds(nx, ny) || !isWalkable(nx, ny) || closedSet[nx][ny]) {
				continue;
			}

			int newGCost = current->gCost + 1;
			int newHCost = manhattanDistance(nx, ny, goalX, goalY);

			if (allNodes[nx][ny] == NULL || newGCost < allNodes[nx][ny]->gCost) {
				NODE* neighbor = (NODE*)malloc(sizeof(NODE));
				if (neighbor == NULL) {
					// Free memory and return if allocation fails
					for (int i = 0; i < GRID_WIDTH; i++) {
						for (int j = 0; j < GRID_HEIGHT; j++) {
							free(allNodes[i][j]);
						}
						free(allNodes[i]);
						free(closedSet[i]);
					}
					free(allNodes);
					free(closedSet);
					return NULL;
				}
				neighbor->x = nx;
				neighbor->y = ny;
				neighbor->gCost = newGCost;
				neighbor->hCost = newHCost;
				neighbor->fCost = newGCost + newHCost;
				neighbor->parent = current;

				if (allNodes[nx][ny] == NULL) {
					pushHeap(&openSet, neighbor);
					allNodes[nx][ny] = neighbor;
				}
				else {
					free(allNodes[nx][ny]);
					allNodes[nx][ny] = neighbor;
				}
			}
		}
	}

	// Free dynamically allocated memory if no path is found
	for (int i = 0; i < GRID_WIDTH; i++) {
		for (int j = 0; j < GRID_HEIGHT; j++) {
			free(allNodes[i][j]);
		}
		free(allNodes[i]);
		free(closedSet[i]);
	}
	free(allNodes);
	free(closedSet);

	return NULL; // No path found
}


I can only think now as a start to create a function that creates a node and substitute that in aStar function like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
NODE* createNode(int x, int y, int gCost, int hCost, NODE* parent) {
	NODE* newNode = (NODE*)malloc(sizeof(NODE));
	if (newNode == NULL) {
		return NULL; // Handle memory allocation failure
	}
	newNode->x = x;
	newNode->y = y;
	newNode->gCost = gCost;
	newNode->hCost = hCost;
	newNode->fCost = gCost + hCost;
	newNode->parent = parent;
	return newNode;
}


Now I'll write here where the aStar is called..
Last edited on
Mif (393)
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
 
// Monster track player
void monsterTrackPlayer(int mobIdx)
{
	if ((gMonster[mobIdx].WorldPos.y > (TOWN_MIN_Y + SCALE_FACTOR)) || (gMonster[mobIdx].WorldPos.x > TOWN_MIN_X)) // town Sud edge
	{
		updateGrid(grid);

		// Convert screen positions to grid coordinates
		int startX = gMonster[mobIdx].ScreenPos.x / SCALE_FACTOR;
		int startY = gMonster[mobIdx].ScreenPos.y / SCALE_FACTOR;
		int goalX = gPlayer.ScreenPos.x / SCALE_FACTOR;
		int goalY = gPlayer.ScreenPos.y / SCALE_FACTOR;

		// Check if the monster is in a position where it should track the player
		if ((gMonster[mobIdx].WorldPos.y > (TOWN_MIN_Y + SCALE_FACTOR)) || (gMonster[mobIdx].WorldPos.x > TOWN_MIN_X)) // town Sud edge
		{
			// Generate the path using A* algorithm
			NODE* path = aStar(startX, startY, goalX, goalY);

			if (path != NULL)
			{
				// Count the number of steps in the path
				int pathLength = 0;
				NODE* currentNode = path;

				while (currentNode != NULL)
				{
					pathLength++;

					if (currentNode->parent != NULL)
					{
						currentNode = currentNode->parent;
					}
					else
					{
						break;
					}
				}

				// Allocate memory to store the path
				NODE** fullPath = (NODE**)malloc(pathLength * sizeof(NODE*));
				if (fullPath == NULL)
				{
					// Handle memory allocation failure
					// Free the nodes in the path
					currentNode = path;
					while (currentNode != NULL)
					{
						NODE* temp = currentNode;
						currentNode = currentNode->parent;
						free(temp);
					}
					return; // Exit if memory allocation fails
				}

				// Trace the path from the goal to the start node
				currentNode = path;
				for (int i = pathLength - 1; i >= 0; i--)
				{
					fullPath[i] = currentNode;
					currentNode = currentNode->parent;
				}

				// Follow the path step by step (ignoring the first node which is the monster's current position)
				if (pathLength > 1)
				{
					NODE* nextStep = fullPath[1]; // The next step in the path

					int dx = nextStep->x * SCALE_FACTOR - gMonster[mobIdx].ScreenPos.x;
					int dy = nextStep->y * SCALE_FACTOR - gMonster[mobIdx].ScreenPos.y;

					followPlayer(dx, dy, mobIdx);
				}

				// Free the allocated memory
				for (int i = 0; i < pathLength; i++)
				{
					free(fullPath[i]);
				}

				free(fullPath);
			}
		}
	}
	else if (gMonster[mobIdx].Directions == UP)
	{
		gMonster[mobIdx].Directions = DOWN;
	}
}


and here I upgrade the grid (map or whatever ..) that represent the current screen which is the player current camera here.

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
 
static void updateGrid(bool map[GRID_HEIGHT][GRID_WIDTH])
{
	// Reset the grid to all false
	for (int i = 0; i < GRID_HEIGHT; i++)
	{
		for (int j = 0; j < GRID_WIDTH; j++)
		{
			map[i][j] = false;
		}
	}

	for (int i = 0; i < GRID_HEIGHT; i++)
	{
		for (int j = 0; j < GRID_WIDTH; j++)
		{
			int mapX = gCamera.x + (SCALE_FACTOR * j);
			int mapY = gCamera.y + (SCALE_FACTOR * i);

			if (mapX >= 0 && mapX < (300 * SCALE_FACTOR) && mapY >= 0 && mapY < (300 * SCALE_FACTOR)) 
			{
				mapX /= SCALE_FACTOR;
				mapY /= SCALE_FACTOR;

				// Ensure mapX and mapY are within 0 to 299 after scaling
				if (mapX < 300 && mapY < 300)
				{
					for (uint32_t Counter = 0; Counter < _countof(gPassableTiles); Counter++)
					{
						if (gOverworld01.TileMap.Map[mapY][mapX] == gPassableTiles[Counter])
						{
							map[i][j] = true;
							break;
						}
					}
				}
			}
		}
	}
}

.. That's it.. and the problem now is that the


// Generate the path using A* algorithm
NODE* path = aStar(startX, startY, goalX, goalY);


from the void monsterTrackPlayer(int mobIdx) function doesn't return a valid node . and it crushes at the statement

 
 
if (currentNode->parent != NULL)


Though i start debugging this and I saw that in aStar function here:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
..
...

NODE* current = popHeap(&openSet);

		if (current->x == goalX && current->y == goalY) {
			// Free dynamically allocated memory when path is found
			for (int i = 0; i < GRID_WIDTH; i++) {
				for (int j = 0; j < GRID_HEIGHT; j++) {
					free(allNodes[i][j]);
				}
				free(allNodes[i]);
				free(closedSet[i]);
			}
			free(allNodes);
			free(closedSet);
			return current;
..
...


the current node it has garbage values and that's not what I want
deleted account xyzzy (5768)
yeahh is quite messy the code

More often than not having code that is properly structured makes fixes and additions a whole lot easier than trying to muck around with "good enough for government" monster code.

A bit of planning from the get-go about structure saves a lot of potentially wasted time trying to dig around in the guts of spaghetti code layout.

Even stepping back and refactoring code for a cleaner layout at this point wouldn't be a waste.

That's muh opinion an' I'm stickin' to it! After almost 30 years dinkin' around with C/C++ code from a self-taught perspective makes it almost imperative to have a game plan before even one line of code is written even for small "this is only a test" snippets.
Mif (393)
Hi george.. well the plan for the game exist.. the problem is that what i've did before was more simplistic but entities didn't worked 100% like I wanted so .. between my game plans and the idea of using A* Algorithm just to make them move from a to b even with obstacles between is a nice thing and well .. just to compute that look how much code it has to be written. Otherwise I have game plan.. :)
Mif (393)
And I still believe that can be done, that is what I wrote some hours ago, and now I just need to make it work 1 time . and I'll refactor the messy code even after.. you're not the only one that dislike that
Duthomhas (13206)
How are you representing the gameboard?
(Number of pixels does not matter when computing A*. Number of _tiles_ matters. Pixels only matter when animating movement.)
jonnin (11437)
statements like this
if (currentNode->parent != NULL)

would be better as

if (currentNode && currentNode->parent) //or you can add the NULL explicit clutter but NULL is zero in all forms of C that I know of

to check both pointers. Your if statment assumes that currentNode is valid here -- and that could be true if you have checked on it recently and blocked around it being null here already. But blocks have a habit of being invalidated over time due to editing and copy pasting, while an explicit check of both pointers will always work... its a type of defensive coding that I feel is necessary for pointers and similar problems (like array indexing) where things go badly wrong in a hurry if there is an error.

I am exploiting the short-circuit feature here: note that reversing the comparison can still crash.

Also self defense, assign ALL pointers to zero or directly to a memory allocation immediately upon creation. I sometimes break the good practice of assigning values to every variable I make but never for pointers.
Last edited on
Duthomhas (13206)
@jonnin
The calloc() function returns zeroed memory, which counts as zeroing pointers on all modern hardware.
jonnin (11437)
Sure, I didn't mean to imply zero from direct assignment was the only way, the important thing is that it is done.
Ganado (6809)
<removed my post since it was just about a typo and doesn't add to the conversation>
Last edited on
jonnin (11437)
typo! You are right, ill fix it above.
Duthomhas (13206)
Hey @Mif, sorry I wasn’t able to be more helpful earlier. I didn’t then know enough about the A* Search algorithm to be more useful.

I played with it a little this last week and wrote a fun little program that you might find useful. The structure of the A* algorithm shows a couple of important features, including data organization and memory usage. https://cplusplus.com/forum/lounge/285881/
Mif (393)
Duthomhas Thank you so much that helped me a lot.. I just need to apply this algorithm to my game which uses only 4 directions so I believe Manhattan algorithm is the best for me .. and then I will need to adapt it to 16 pixel per tile... that's a lot of work .. I'll see what I can do.
Duthomhas (13206)
The directions of travel is a parameter of the A* algorithm. I implemented it as a simple lookup table. You can make it horizontal and vertical movement only by simply removing the diagonal stuff:

154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
XY directions[] =
{
	            {  0, -1 },
	{ -1,  0 },             { +1,  0 },
	            {  0, +1 },
};

bool is_diagonal[] =
{
	      false,
	false,       false,
	      false,
};

const int NUM_DIRECTIONS = sizeof(directions) / sizeof(directions[0]);

For a more advanced graph you would pass it to A* as a function returning a list of locations adjacent to the current location (which would solve the “is walkable to” question as well).

(For my version, diagonal-ness only matters for walking around walls. You will have to adjust your algorithm to fit your needs.)
Last edited on
deleted account xyzzy (5768)
I found a lot of info and a few C implementations for the A* Search algorithm on the interwebz:

https://duckduckgo.com/?t=ffab&q=a*+search+in+c&atb=v188-1&ia=web

I can't say whether the info is useful since I have only done a cursory glance at a couple of links. This one seems to be helpful:

https://codingclutch.com/a-star-algorithm-explanation-implement-in-c/

For me personally I'd be looking for C++ implementations as well as C ones.

https://duckduckgo.com/?q=a*+search+in+c+and+c%2B%2B&t=ffab&atb=v188-1&ia=web

Peace! I'm out'ta here!
Topic archived. No new replies allowed.