Bug Summary

File:c:\siege\siege/src/siege/ai/grid.c
Location:line 103, column 28
Description:Dereference of undefined pointer value

Annotated Source Code

1/*
2 * Copyright (c) 2007 SIEGE Development Team
3 * All rights reserved.
4 *
5 * This file is part of libSIEGE.
6 *
7 * This software is copyrighted work licensed under the terms of the
8 * 2-clause BSD license. Please consult the file "license.txt" for
9 * details.
10 *
11 * If you did not recieve the file with this program, please email
12 * Tim Chas <darkuranium@gmail.com>.
13 */
14
15#define SG_BUILD_LIBRARY
16#include <siege/ai/grid.h>
17
18#include <stdlib.h>
19#include <math.h>
20
21float SG_CALL__cdecl _sgNavGridG(SGAStarNode* from, SGAStarNode* to)
22{
23 SGNavGridData* fdata = from->data;
24 SGNavGridData* tdata = to->data;
25
26 float dx = tdata->x - (float)fdata->x;
27 float dy = tdata->y - (float)fdata->y;
28 return from->score.g + sqrt(dx*dx + dy*dy) * tdata->cost;
29}
30float SG_CALL__cdecl _sgNavGridH(SGAStarNode* from, SGAStarNode* to)
31{
32 SGNavGridData* fdata = from->data;
33 SGNavGridData* tdata = to->data;
34
35 float dx = tdata->x - (float)fdata->x;
36 float dy = tdata->y - (float)fdata->y;
37 return sqrt(dx*dx + dy*dy);
38}
39SGbool SG_CALL__cdecl _sgNavGridGoal(SGAStarNode* from, SGAStarNode* to)
40{
41 return from == to;
42}
43
44SGNavGrid* SG_CALL__cdecl sgNavGridCreate(SGuint width, SGuint height, SGbool diag, SGbool wdiag)
45{
46 SGuint x, y;
47 SGNavGridData* data;
48 SGNavGrid* grid = malloc(sizeof(SGNavGrid));
49 grid->search = NULL((void*)0);
50 grid->grid = malloc((width + 2) * sizeof(SGAStarNode**));
51 grid->width = width;
52 grid->height = height;
53 grid->path = sgListCreate();
54 grid->start = NULL((void*)0);
55 grid->goal = NULL((void*)0);
56
57 grid->diag = diag;
58 grid->wdiag = wdiag;
59
60 for(x = 0; x < width + 2; x++)
1
Loop condition is true. Entering loop body
→
3
←
Loop condition is false. Execution continues on line 73
→
61 {
62 grid->grid[x] = malloc((height + 2) * sizeof(SGAStarNode*));
63 for(y = 0; y < height + 2; y++)
2
←
Loop condition is false. Execution continues on line 60
→
64 {
65 data = malloc(sizeof(SGNavGridData));
66 data->x = x - 1;
67 data->y = y - 1;
68 data->type = SG_NAVGRID_CLEAR0;
69 data->cost = 1.0;
70 grid->grid[x][y] = sgAStarNodeCreate(data);
71 }
72 }
73 for(x = 1; x < width + 1; x++)
4
←
Loop condition is false. Execution continues on line 92
→
74 {
75 for(y = 1; y < height + 1; y++)
76 {
77 sgAStarNodeLink(grid->grid[x][y], grid->grid[x ][y+1]);
78 sgAStarNodeLink(grid->grid[x][y], grid->grid[x-1][y ]);
79 sgAStarNodeLink(grid->grid[x][y], grid->grid[x ][y-1]);
80 sgAStarNodeLink(grid->grid[x][y], grid->grid[x+1][y ]);
81 if(diag)
82 {
83 sgAStarNodeLink(grid->grid[x][y], grid->grid[x-1][y+1]);
84 sgAStarNodeLink(grid->grid[x][y], grid->grid[x-1][y-1]);
85 sgAStarNodeLink(grid->grid[x][y], grid->grid[x+1][y-1]);
86 sgAStarNodeLink(grid->grid[x][y], grid->grid[x+1][y+1]);
87 }
88 }
89 }
90
91 // unlinking borders...
92 for(x = 1; x < width + 1; x++)
5
←
Loop condition is false. Execution continues on line 101
→
93 {
94 sgAStarNodeDUnlink(grid->grid[x-1][1 ], grid->grid[x][0 ]);
95 sgAStarNodeDUnlink(grid->grid[x ][1 ], grid->grid[x][0 ]);
96 sgAStarNodeDUnlink(grid->grid[x+1][1 ], grid->grid[x][0 ]);
97 sgAStarNodeDUnlink(grid->grid[x-1][height], grid->grid[x][height+1]);
98 sgAStarNodeDUnlink(grid->grid[x ][height], grid->grid[x][height+1]);
99 sgAStarNodeDUnlink(grid->grid[x+1][height], grid->grid[x][height+1]);
100 }
101 for(y = 1; y < height + 1; y++)
6
←
Loop condition is true. Entering loop body
→
102 {
103 sgAStarNodeDUnlink(grid->grid[1 ][y+1], grid->grid[0 ][y]);
7
←
Dereference of undefined pointer value
104 sgAStarNodeDUnlink(grid->grid[1 ][y ], grid->grid[0 ][y]);
105 sgAStarNodeDUnlink(grid->grid[1 ][y-1], grid->grid[0 ][y]);
106 sgAStarNodeDUnlink(grid->grid[width][y+1], grid->grid[width+1][y]);
107 sgAStarNodeDUnlink(grid->grid[width][y ], grid->grid[width+1][y]);
108 sgAStarNodeDUnlink(grid->grid[width][y-1], grid->grid[width+1][y]);
109 }
110 sgAStarNodeDUnlink(grid->grid[1 ][1 ], grid->grid[0 ][0 ]);
111 sgAStarNodeDUnlink(grid->grid[1 ][height], grid->grid[0 ][height+1]);
112 sgAStarNodeDUnlink(grid->grid[width][height], grid->grid[width+1][height+1]);
113 sgAStarNodeDUnlink(grid->grid[width][1 ], grid->grid[width+1][0 ]);
114
115 return grid;
116}
117void SG_CALL__cdecl sgNavGridDestroy(SGNavGrid* grid)
118{
119 sgListDestroy(grid->path);
120 size_t x, y;
121 for(x = 0; x < grid->width + 2; x++)
122 {
123 for(y = 0; y < grid->height + 2; y++)
124 {
125 free(grid->grid[x][y]->data);
126 sgAStarNodeDestroy(grid->grid[x][y]);
127 }
128 free(grid->grid[x]);
129 }
130 free(grid->grid);
131 if(grid->search != NULL((void*)0))
132 sgAStarDestroy(grid->search);
133 free(grid);
134}
135SGAStarNode* SG_CALL__cdecl sgNavGridGetNode(SGNavGrid* grid, SGuint x, SGuint y)
136{
137 if(x >= grid->width || y >= grid->height)
138 return NULL((void*)0);
139 return grid->grid[x+1][y+1];
140}
141SGNavGridData* SG_CALL__cdecl sgNavGridGetData(SGNavGrid* grid, SGuint x, SGuint y)
142{
143 SGAStarNode* node = sgNavGridGetNode(grid, x, y);
144 if(node == NULL((void*)0))
145 return NULL((void*)0);
146 return node->data;
147}
148void SG_CALL__cdecl sgNavGridAddClear(SGNavGrid* grid, SGuint x, SGuint y)
149{
150 SGAStarNode* node = sgNavGridGetNode(grid, x, y);
151 if(node != NULL((void*)0))
152 {
153 ((SGNavGridData*)node->data)->type = SG_NAVGRID_CLEAR0;
154 x++;
155 y++;
156 sgAStarNodeLink(grid->grid[x ][y+1], grid->grid[x][y]);
157 sgAStarNodeLink(grid->grid[x-1][y ], grid->grid[x][y]);
158 sgAStarNodeLink(grid->grid[x ][y-1], grid->grid[x][y]);
159 sgAStarNodeLink(grid->grid[x+1][y ], grid->grid[x][y]);
160 if(grid->diag)
161 {
162 if(grid->wdiag || ((((SGNavGridData*)grid->grid[x ][y+1]->data)->type != SG_NAVGRID_WALL1)
163 && (((SGNavGridData*)grid->grid[x-1][y ]->data)->type != SG_NAVGRID_WALL1)))
164 sgAStarNodeLink(grid->grid[x-1][y+1], grid->grid[x][y]);
165 if(grid->wdiag || ((((SGNavGridData*)grid->grid[x ][y-1]->data)->type != SG_NAVGRID_WALL1)
166 && (((SGNavGridData*)grid->grid[x-1][y ]->data)->type != SG_NAVGRID_WALL1)))
167 sgAStarNodeLink(grid->grid[x-1][y-1], grid->grid[x][y]);
168 if(grid->wdiag || ((((SGNavGridData*)grid->grid[x ][y-1]->data)->type != SG_NAVGRID_WALL1)
169 && (((SGNavGridData*)grid->grid[x+1][y ]->data)->type != SG_NAVGRID_WALL1)))
170 sgAStarNodeLink(grid->grid[x+1][y-1], grid->grid[x][y]);
171 if(grid->wdiag || ((((SGNavGridData*)grid->grid[x ][y+1]->data)->type != SG_NAVGRID_WALL1)
172 && (((SGNavGridData*)grid->grid[x+1][y ]->data)->type != SG_NAVGRID_WALL1)))
173 sgAStarNodeLink(grid->grid[x+1][y+1], grid->grid[x][y]);
174 }
175 if(!grid->wdiag)
176 {
177 if(((SGNavGridData*)grid->grid[x ][y+1]->data)->type != SG_NAVGRID_WALL1)
178 {
179 if(((SGNavGridData*)grid->grid[x-1][y+1]->data)->type != SG_NAVGRID_WALL1)
180 sgAStarNodeLink(grid->grid[x-1][y ], grid->grid[x ][y+1]);
181 if(((SGNavGridData*)grid->grid[x+1][y+1]->data)->type != SG_NAVGRID_WALL1)
182 sgAStarNodeLink(grid->grid[x+1][y ], grid->grid[x ][y+1]);
183 }
184 if(((SGNavGridData*)grid->grid[x-1][y ]->data)->type != SG_NAVGRID_WALL1)
185 {
186 if(((SGNavGridData*)grid->grid[x-1][y+1]->data)->type != SG_NAVGRID_WALL1)
187 sgAStarNodeLink(grid->grid[x ][y+1], grid->grid[x-1][y ]);
188 if(((SGNavGridData*)grid->grid[x-1][y-1]->data)->type != SG_NAVGRID_WALL1)
189 sgAStarNodeLink(grid->grid[x ][y-1], grid->grid[x-1][y ]);
190 }
191 if(((SGNavGridData*)grid->grid[x ][y-1]->data)->type != SG_NAVGRID_WALL1)
192 {
193 if(((SGNavGridData*)grid->grid[x-1][y-1]->data)->type != SG_NAVGRID_WALL1)
194 sgAStarNodeLink(grid->grid[x-1][y ], grid->grid[x ][y-1]);
195 if(((SGNavGridData*)grid->grid[x+1][y-1]->data)->type != SG_NAVGRID_WALL1)
196 sgAStarNodeLink(grid->grid[x+1][y ], grid->grid[x ][y-1]);
197 }
198 if(((SGNavGridData*)grid->grid[x+1][y ]->data)->type != SG_NAVGRID_WALL1)
199 {
200 if(((SGNavGridData*)grid->grid[x+1][y+1]->data)->type != SG_NAVGRID_WALL1)
201 sgAStarNodeLink(grid->grid[x ][y+1], grid->grid[x+1][y ]);
202 if(((SGNavGridData*)grid->grid[x+1][y-1]->data)->type != SG_NAVGRID_WALL1)
203 sgAStarNodeLink(grid->grid[x ][y-1], grid->grid[x+1][y ]);
204 }
205 }
206 }
207}
208void SG_CALL__cdecl sgNavGridAddWall(SGNavGrid* grid, SGuint x, SGuint y)
209{
210 SGAStarNode* node = sgNavGridGetNode(grid, x, y);
211 if(node != NULL((void*)0))
212 {
213 ((SGNavGridData*)node->data)->type = SG_NAVGRID_WALL1;
214 x++;
215 y++;
216 sgAStarNodeUnlink(grid->grid[x ][y+1], grid->grid[x][y]);
217 sgAStarNodeUnlink(grid->grid[x-1][y ], grid->grid[x][y]);
218 sgAStarNodeUnlink(grid->grid[x ][y-1], grid->grid[x][y]);
219 sgAStarNodeUnlink(grid->grid[x+1][y ], grid->grid[x][y]);
220 if(grid->diag)
221 {
222 sgAStarNodeUnlink(grid->grid[x-1][y+1], grid->grid[x][y]);
223 sgAStarNodeUnlink(grid->grid[x-1][y-1], grid->grid[x][y]);
224 sgAStarNodeUnlink(grid->grid[x+1][y-1], grid->grid[x][y]);
225 sgAStarNodeUnlink(grid->grid[x+1][y+1], grid->grid[x][y]);
226 }
227 if(!grid->wdiag)
228 {
229 sgAStarNodeUnlink(grid->grid[x ][y+1], grid->grid[x-1][y ]);
230 sgAStarNodeUnlink(grid->grid[x ][y+1], grid->grid[x+1][y ]);
231 sgAStarNodeUnlink(grid->grid[x-1][y ], grid->grid[x ][y+1]);
232 sgAStarNodeUnlink(grid->grid[x-1][y ], grid->grid[x ][y-1]);
233 sgAStarNodeUnlink(grid->grid[x ][y-1], grid->grid[x-1][y ]);
234 sgAStarNodeUnlink(grid->grid[x ][y-1], grid->grid[x+1][y ]);
235 sgAStarNodeUnlink(grid->grid[x+1][y ], grid->grid[x ][y+1]);
236 sgAStarNodeUnlink(grid->grid[x+1][y ], grid->grid[x ][y-1]);
237 }
238 }
239}
240void SG_CALL__cdecl sgNavGridAddStart(SGNavGrid* grid, SGuint x, SGuint y)
241{
242 SGAStarNode* node = sgNavGridGetNode(grid, x, y);
243 if(node != NULL((void*)0))
244 {
245 ((SGNavGridData*)node->data)->type = SG_NAVGRID_START2;
246 grid->start = node;
247 }
248}
249void SG_CALL__cdecl sgNavGridAddGoal(SGNavGrid* grid, SGuint x, SGuint y)
250{
251 SGAStarNode* node = sgNavGridGetNode(grid, x, y);
252 if(node != NULL((void*)0))
253 {
254 ((SGNavGridData*)node->data)->type = SG_NAVGRID_GOAL3;
255 grid->goal = node;
256 }
257}
258void SG_CALL__cdecl sgNavGridSearchCreate(SGNavGrid* grid)
259{
260 if(grid->search != NULL((void*)0))
261 sgAStarDestroy(grid->search);
262 size_t x, y;
263 for(x = 0; x < grid->width + 2; x++)
264 for(y = 0; y < grid->height + 2; y++)
265 grid->grid[x][y]->from = NULL((void*)0);
266 grid->search = sgAStarCreate(grid->start, grid->goal, _sgNavGridG, _sgNavGridH, _sgNavGridGoal);
267}
268SGbool SG_CALL__cdecl sgNavGridSearchStep(SGNavGrid* grid)
269{
270 return sgAStarStep(grid->search);
271}
272SGbool SG_CALL__cdecl sgNavGridGoalFound(SGNavGrid* grid)
273{
274 return sgAStarGoalFound(grid->search);
275}
276SGList* SG_CALL__cdecl sgNavGridSearchPath(SGNavGrid* grid, size_t* pathlen)
277{
278 sgListDestroy(grid->path);
279 grid->path = sgListCreate();
280
281 SGList* list = sgAStarPath(grid->search, pathlen);
282 SGListNode* node;
283 SGAStarNode* anode;
284
285 for(node = list->head; node != NULL((void*)0); node = node->next)
286 {
287 anode = node->item;
288 sgListAppend(grid->path, anode->data);
289 }
290
291 return grid->path;
292}