Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 425 lines (343 sloc) 14.195 kb
43797aa @pokeb Initial commit
authored
1 //
2 // ASISpaceTimePathFinder.m
3 // Part of ASIPathFinder --> http://allseeing-i.com/ASIPathFinder
4 //
5 // Created by Ben Copsey on 20/03/2009.
6 // Copyright 2009 All-Seeing Interactive. All rights reserved.
7 //
8
9 #import "ASISpaceTimePathFinder.h"
10 #import "ASISpatialPathAssessor.h"
11 #import "ASIWorldMap.h"
afef113 @pokeb Lots of changes, getting ready for proper release
authored
12 #import "ASIUnit.h"
43797aa @pokeb Initial commit
authored
13 #import "ASIPath.h"
14 #import "ASISpaceTimeMap.h"
15 #import "ASISearchNodeList.h"
afef113 @pokeb Lots of changes, getting ready for proper release
authored
16 #import "ASITeam.h"
43797aa @pokeb Initial commit
authored
17
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
18 // Since only one object ever plans at once, we store the list of positions we've already looked at in a static array
19 // If you were threading path finding (which I would strongly advise against) you need to allocate storage for this differently
43797aa @pokeb Initial commit
authored
20 static BOOL *searchedPositions = NULL;
21 static unsigned int lastMapSize = 0;
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
22
23 // Controls the order in which we'll search positions
24 // This basically means we search our current position first (since a great deal of the time, we're actually path finding to stay still!)
43797aa @pokeb Initial commit
authored
25 static char positions[3] = {0,-1,1};
26
27 @implementation ASISpaceTimePathFinder
28
29 static unsigned char searchDirections[8] = {PathDirectionNorthEast,PathDirectionSouthWest,PathDirectionNorthWest,PathDirectionNorth,PathDirectionWest,PathDirectionSouthEast,PathDirectionEast,PathDirectionSouth};
30
afef113 @pokeb Lots of changes, getting ready for proper release
authored
31 - (id)initWithObject:(ASIUnit *)newObject;
43797aa @pokeb Initial commit
authored
32 {
33 self = [super init];
34 [self setObject:newObject];
35 return self;
36 }
37
38 - (ASIPath *)findPath
39 {
40 ASIWorldMap *map = [object map];
afef113 @pokeb Lots of changes, getting ready for proper release
authored
41 ASISpaceTimeMap *spaceTimeMap = [[object team] spaceTimeMap];
43797aa @pokeb Initial commit
authored
42 int timeSize = [spaceTimeMap timeSpan];
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
43
44 // If the object is planning part way through the pre-calculated timespan, we need to remove its current path
45 unsigned char currentTimeStep = [spaceTimeMap currentTimeStep];
46 if (currentTimeStep) {
47 while ([[object path] length]) {
48 Position3D pos = [[object path] firstNode];
49 [spaceTimeMap removeObject:object atPositionIndefinitely:CGPointMake(pos.x,pos.y) fromTime:currentTimeStep];
50 [[object path] removeFirstNode];
51 }
52 }
53
54 // Clear the object's path
55 ASIPath *path = [object path];
56 if (!path) {
57 [object setPath:[[[ASIPath alloc] initWithPathSize:timeSize] autorelease]];
58 path = [object path];
59 } else {
60 [path clear];
61 }
62
43797aa @pokeb Initial commit
authored
63 Size3D size = [map mapSize];
64 int sizeXByY = size.xSize*size.ySize;
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
65 ASISpatialPathAssessor *spatialPathAssessor = [object pathAssessment];
43797aa @pokeb Initial commit
authored
66
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
67 // Allocate storage for a map of positions we've already looked at, if we haven't already, or we're path finding on a different sized map
43797aa @pokeb Initial commit
authored
68 unsigned int mapSize = sizeXByY*(timeSize+1);
69 if (!searchedPositions || lastMapSize != mapSize) {
70 if (searchedPositions) {
71 free(searchedPositions);
72 }
73 if ((searchedPositions = (BOOL *)calloc(mapSize,sizeof(BOOL))) == NULL ) {
74 NSLog(@"Out of memory!!!");
75 return nil;
76 }
77 lastMapSize = mapSize;
78 } else {
79 memset(searchedPositions, 0, mapSize);
80 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
81
82 // An object's speed governs how many time steps it needs to move from one position to another
83 // An object with a speed of 1 moves in a single time step, while a speed of 2 is half the speed, and takes two time steps to perform the same move
43797aa @pokeb Initial commit
authored
84 int speed = [object speed];
85
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
86
43797aa @pokeb Initial commit
authored
87 Position3D origin = [object position];
88 Position3D destination = [object destination];
89 if (attemptToStayInSameLocation) {
90 destination = origin;
91 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
92
93 // Record our current position, so units don't try to swap positions in a head-on collision
43797aa @pokeb Initial commit
authored
94 int i;
95 for (i=0; i<speed; i++) {
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
96 [spaceTimeMap setObject:object atPosition:Position3DMake(origin.x,origin.y,currentTimeStep+i)];
43797aa @pokeb Initial commit
authored
97 }
98 ASISearchNodeList *nodeList = [[ASISearchNodeList alloc] init];
99
100
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
101 // Create a new node to store our starting position
43797aa @pokeb Initial commit
authored
102 Node *node = nodeAlloc();
103 node->time = 0;
104 node->position = origin;
105 node->distance = [spatialPathAssessor realDistanceFromDestination:origin];
106 [nodeList addNode:node];
107
108 int x,y;
109
110 Position3D position;
111 Position3D nodePosition;
afef113 @pokeb Lots of changes, getting ready for proper release
authored
112 ASIMapObject *mapObject;
43797aa @pokeb Initial commit
authored
113 float distance;
114 float cost;
115 unsigned char time;
116 unsigned char searchDirection;
117 char directionCounter;
118 int searched = 0;
119 int costPos;
120 Node *nearestNodeSoFar = NULL;
121
afef113 @pokeb Lots of changes, getting ready for proper release
authored
122 ASIMapObject *objectAtPosition = nil;
43797aa @pokeb Initial commit
authored
123
124 BOOL atDestination;
125 BOOL canStayHere;
126 BOOL shouldStop = NO;
127
128 signed char searchZ = 0;
129
130 int xPos, yPos;
131
132 while ([nodeList length]) {
133
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
134 // Grab the first node from the list (it will always be the best node to look at next
43797aa @pokeb Initial commit
authored
135 node = nodeAlloc();
136 *node = *[nodeList firstNode];
137 [nodeList removeFirstNode];
138
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
139 // If we're at the boundary of our time span, we don't need to plan any further from here
43797aa @pokeb Initial commit
authored
140 if (node->time > timeSize-speed) {
141 continue;
142 }
143 time = node->time+speed;
144 searched++;
145
146
147 nodePosition = node->position;
148 directionCounter = -1;
149
150 // We need to look at position (0,0) first, as a lot of the time we need to stay still
151 for (xPos = 0; xPos<3; xPos++) {
152 for (yPos=0; yPos<3; yPos++) {
153
154 x = positions[xPos];
155 y = positions[yPos];
156
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
157 // Create a position for the place we're looking at
43797aa @pokeb Initial commit
authored
158 position = Position3DMake(nodePosition.x+x,nodePosition.y+y,searchZ);
159
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
160 // If we aren't staying still, the direction we're travelling in
43797aa @pokeb Initial commit
authored
161 if (x != 0 || y != 0) {
162 directionCounter++;
163 searchDirection = searchDirections[directionCounter];
164 }
165
166 // Are we out of bounds?
167 if (position.x < 0 || position.x > size.xSize-1 || position.y < 0 || position.y > size.ySize-1) {
168 continue;
169 }
170
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
171
172 // Have we searched this node already?
173 costPos = position.x+(position.y*size.xSize)+(sizeXByY*time);
174 if (searchedPositions[costPos]) {
175 continue;
176 }
177
178 // If we're staying still, our cost will be the same as our parent node
43797aa @pokeb Initial commit
authored
179 if (x==0 && y==0) {
180 cost = node->cost;
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
181 // Otherwise, increase our cost by one
43797aa @pokeb Initial commit
authored
182 } else {
183 cost = node->cost+1;
184 }
185
186
187 //Look for a building at this point
188 mapObject = [map objectAtPosition:position];
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
189 if (mapObject && mapObject != object) {
190 if (![mapObject isPassableByObject:object movingNow:YES atPosition:&position fromPosition:&nodePosition withCost:&cost andDistance:&distance]) {
43797aa @pokeb Initial commit
authored
191 continue;
192 }
193 }
194
195
196 if (x != 0 || y != 0) {
197 //Stop paths hugging corners
198 switch (searchDirection) {
199 case PathDirectionNorth:
200 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x-1,nodePosition.y,0)];
201 if (mapObject && ![mapObject allowsCornerCutting]) {
202 continue;
203 }
204 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x,nodePosition.y-1,0)];
205 if (mapObject && ![mapObject allowsCornerCutting]) {
206 continue;
207 }
208 break;
209 case PathDirectionWest:
210 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x-1,nodePosition.y,0)];
211 if (mapObject && ![mapObject allowsCornerCutting]) {
212 continue;
213 }
214 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x,nodePosition.y+1,0)];
215 if (mapObject && ![mapObject allowsCornerCutting]) {
216 continue;
217 }
218 break;
219 case PathDirectionEast:
220 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x+1,nodePosition.y,0)];
221 if (mapObject && ![mapObject allowsCornerCutting]) {
222 continue;
223 }
224 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x,nodePosition.y-1,0)];
225 if (mapObject && ![mapObject allowsCornerCutting]) {
226 continue;
227 }
228 break;
229 case PathDirectionSouth:
230 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x+1,nodePosition.y,0)];
231 if (mapObject && ![mapObject allowsCornerCutting]) {
232 continue;
233 }
234 mapObject = [map objectAtPosition:Position3DMake(nodePosition.x,nodePosition.y+1,0)];
235 if (mapObject && ![mapObject allowsCornerCutting]) {
236 continue;
237 }
238 break;
239 }
240 }
241
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
242 // If we've arrived here, this position is valid to travel to, let's record the cost
43797aa @pokeb Initial commit
authored
243 searchedPositions[costPos] = YES;
244
245
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
246 // Now look at the space time map to see if any other units have already reserved this position at this time step
247 unsigned int i = 0;
248 BOOL positionAlreadyReserved = NO;
249 for (i=0; i<speed; i++) {
250 objectAtPosition = [spaceTimeMap objectAtPosition:Position3DMake(position.x,position.y,time+i)];
251 if (objectAtPosition && objectAtPosition != object) {
252 // An object has already reserved this position
253 positionAlreadyReserved = YES;
254 break;
255
256 } else {
257 objectAtPosition =[spaceTimeMap objectAtPosition:Position3DMake(position.x,position.y,node->time+i)];
258 if (objectAtPosition && objectAtPosition != object && objectAtPosition == [spaceTimeMap objectAtPosition:Position3DMake(node->position.x,node->position.y,time+i)]) {
259 // The object at this position at the last time step is going to move to the space we are currently in.
260 // This would be a head-on collision, so we need to ignore this position continue looking
261 positionAlreadyReserved = YES;
262 break;
263 }
43797aa @pokeb Initial commit
authored
264 }
265 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
266 if (positionAlreadyReserved) {
267 continue;
268 }
269
43797aa @pokeb Initial commit
authored
270
271
272
273 atDestination = NO;
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
274
275 // If we're moving to attack an object, we don't need to reach the destination - we only need to get within range of it
43797aa @pokeb Initial commit
authored
276 if (stopWhenWithinRangeOfTarget && [object isObjectWithinLineOfFire:[object target] ifWeWereAt:position]) {
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
277
278 // This position is within range of the target
43797aa @pokeb Initial commit
authored
279 distance = 0;
280 cost = node->cost;
281 atDestination = YES;
282 if (time == timeSize) {
283 shouldStop = YES;
284 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
285
286 // Have we reached the destination?
43797aa @pokeb Initial commit
authored
287 } else if (EqualPositions(position, destination)) {
288 distance = 0;
289 cost = node->cost;
290 atDestination = YES;
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
291
292
43797aa @pokeb Initial commit
authored
293 } else {
294
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
295 // Get the distance to the destination from the path assessor
43797aa @pokeb Initial commit
authored
296 distance = [spatialPathAssessor realDistanceFromDestination:position];
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
297
43797aa @pokeb Initial commit
authored
298 //Make sure the spatial assessor looked at this node
299 if (distance == 0) {
300
301 // If not, we'll just add one to the current node distance, which should be accurate enough for most purposes
302 distance = node->distance+1;
303 }
304
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
305 // Increase the cost slightly if we've had to change direction to get here
306 // This stops us zigzagging around
307 if (searchDirection != node->direction) {
43797aa @pokeb Initial commit
authored
308 cost +=0.25f;
309 }
310
311 }
312
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
313 // This is valid position to move to at this timestep
314 // Add the node to the search list
43797aa @pokeb Initial commit
authored
315 Node *n = nodeAlloc();
316 n->parentNode = node;
317 n->position = position;
318 n->distance = distance;
319 n->cost = cost;
320 n->time = time;
321 n->direction = searchDirection;
322 [nodeList addNode:n];
323 canStayHere = NO;
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
324
43797aa @pokeb Initial commit
authored
325
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
326 // If we've arrived at the destination, but are not on the final time step, let's just look forward in time to see if we can stay at this position
327 // This means we only need to look at a single node if we're planning to stay still
328 if (atDestination && time < timeSize) {
329
330 shouldStop = YES;
43797aa @pokeb Initial commit
authored
331 for (i=time; i< timeSize; i++) {
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
332 unsigned int i2;
333 for (i2=0; i2<speed; i2++) {
334 objectAtPosition = [spaceTimeMap objectAtPosition:Position3DMake(position.x,position.y,i+i2)];
335 if (objectAtPosition && objectAtPosition != object) {
336 atDestination = NO;
337 shouldStop = NO;
338 break;
339 }
43797aa @pokeb Initial commit
authored
340 }
e833345 @pokeb Final tweaks for release
authored
341 if (!shouldStop) {
342 break;
343 }
43797aa @pokeb Initial commit
authored
344 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
345 if (shouldStop) {
346 nearestNodeSoFar = n;
43797aa @pokeb Initial commit
authored
347 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
348
349 // We haven't reached the destination, but we're at the final time step for planning
350 // If we are nearer than we've ever been before to the target, make this the nearest node
351 } else if ((time == timeSize && (!nearestNodeSoFar || distance < nearestNodeSoFar->distance))) {
352 nearestNodeSoFar = n;
43797aa @pokeb Initial commit
authored
353 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
354
43797aa @pokeb Initial commit
authored
355 if (shouldStop) {
356 break;
357 }
358
359 }
360 if (shouldStop) {
361 break;
362 }
363 }
364 if (shouldStop) {
365 break;
366 }
367 }
368
369 if (!nearestNodeSoFar) {
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
370 // We have failed to find any kind of path. This might happen if we're completely hemmed in
43797aa @pokeb Initial commit
authored
371 freeNodes();
372 [nodeList release];
373 return nil;
374 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
375
376 // If we get here, we at least have a partial path to the destination, if not a full path
377 // We start with the node that we found to be nearest to our destination, and work backwards through its parent nodes to construct a path
43797aa @pokeb Initial commit
authored
378 node = nearestNodeSoFar;
379
380
381
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
382 // Reserve our final position on the space time map
383 // If we ended up at this node part way through the time span, we'll reserve this node for the rest of the time span, starting from the time we got here
384 [spaceTimeMap setObject:object atPositionIndefinitely:CGPointMake(node->position.x,node->position.y) fromTime:node->time];
43797aa @pokeb Initial commit
authored
385
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
386 // Now loop through the parent nodes, constructing our path (by adding each parent to the start of the path)
387 // and reserving the positions on the space time map
43797aa @pokeb Initial commit
authored
388 while (node->parentNode && node->parentNode != node) {
389
390 [path insertNodeAtStart:node->position];
391
392 if (speed == 2) {
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
393 [spaceTimeMap setObject:object atPosition:Position3DMake(node->position.x,node->position.y,node->time-1)];
394 [spaceTimeMap setObject:object atPosition:Position3DMake(node->position.x,node->position.y,node->time)];
395 [spaceTimeMap setObject:object atPosition:Position3DMake(node->position.x,node->position.y,node->time+1)];
396 [spaceTimeMap setObject:object atPosition:Position3DMake(node->position.x,node->position.y,node->time+2)];
43797aa @pokeb Initial commit
authored
397 } else {
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
398 [spaceTimeMap setObject:object atPosition:Position3DMake(node->position.x,node->position.y,node->time)];
399 [spaceTimeMap setObject:object atPosition:Position3DMake(node->position.x,node->position.y,node->time+1)];
43797aa @pokeb Initial commit
authored
400 }
401
402 node = node->parentNode;
403 }
404
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
405 // If we were moving to attack a target, and we got in range of it, let's set the object's destination to the position we will arrive at
43797aa @pokeb Initial commit
authored
406 if (stopWhenWithinRangeOfTarget > 0 && [object isObjectWithinLineOfFire:[object target] ifWeWereAt:nearestNodeSoFar->position]) {
407 [object setDestination:nearestNodeSoFar->position];
408 }
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
409
410 // free all the nodes we allocated on the heap
43797aa @pokeb Initial commit
authored
411 freeNodes();
1b3d56c @pokeb Continue work merging in Space Harvest stuff
authored
412
413 // Get rid of our search list
43797aa @pokeb Initial commit
authored
414 [nodeList release];
415 return path;
416
417 }
418
419
420
421 @synthesize object;
422 @synthesize stopWhenWithinRangeOfTarget;
423 @synthesize attemptToStayInSameLocation;
424 @end
Something went wrong with that request. Please try again.