· 9 years ago · Jan 27, 2017, 07:06 PM
1#! /usr/bin/env python3
2# coding: utf-8
3
4# pathfinder.py, a python pathfinder and demo by
5# James Spencer <jamessp [at] gmail.com>.
6
7# To the extent possible under law, the person who associated CC0 with
8# pathfinder.py has waived all copyright and related or neighboring rights
9# to pathfinder.py.
10
11# You should have received a copy of the CC0 legalcode along with this
12# work. If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13
14from __future__ import print_function
15from __future__ import division
16from __future__ import unicode_literals
17from collections import deque
18import heapq
19
20
21class Config(object):
22 '''This class is a minimal subset of <config.py> from my project, and much
23 of the data herein was parsed from config files, hence the irregular
24 naming. Feel free top plop the dicts into a <config.py> of your own and
25 import it.
26 '''
27
28 def __init__(self):
29 self.TERRAIN_CHARACTERS = {'open secret door' : '~',
30 'closed secret door' : '§',
31 'flagstone' : '.',
32 'stone brick' : '#',
33 'closed door' : '+',
34 'open door' : '-',
35 'solid stone' : '&'}
36 self.TERRAIN_COLORS = {'closed door' : 'aqua',
37 'flagstone' : 'silver',
38 'open secret door' : 'aqua',
39 'open door' : 'aqua',
40 'solid stone' : 'black',
41 'stone brick' : 'white',
42 'closed secret door' : 'aqua'}
43 # NOTE: This could easily be a dict where the keys are the obstructions
44 # and the values are the tile characters, pygame surfaces, etc.
45 self.OBSTRUCTION_CHARACTERS = {'closed secret door', 'stone brick',
46 'closed door', 'solid stone'}
47 # 16 of the DB32 colors, as they are easier on the eyes than VGA16.
48 self.COLORNAMES = {'white': (255, 255, 255),
49 'yellow': (251, 242, 54),
50 'fuchsia': (215, 123, 186),
51 'red': (172, 50, 50),
52 'silver': (155, 173, 183),
53 'gray': (105, 106, 106),
54 'olive': (143, 151, 74),
55 'purple': (118, 66, 138),
56 'maroon': (102, 57, 49),
57 'aqua': (96, 205, 228),
58 'lime': (153, 229, 80),
59 'teal': (48, 96, 130),
60 'green': (75, 105, 47),
61 'blue': (91, 110, 225),
62 'navy': (63, 63, 116),
63 'black': (0, 0, 0)}
64
65
66# To 'fake' my projects <config.py>
67config = Config()
68
69
70class Area(object):
71 '''The relevant to pathfinding bits of my project's Area() class. See
72 the example at the end to see how this is used.
73 '''
74
75 def __init__(self):
76 self.terrain = None
77 self.width = None
78 self.height = None
79
80
81class Pathfinder(object):
82 '''Find a path form x1, y1 to a point or tile(s).
83
84 area -- An instance of the Area() class. See Area() at the top, and the
85 pygame example at the end of the file for a minimal implementation.
86 c_dist -- Integer or Double, the distance of a step in a cardinal
87 direction.
88 d_dist -- Integer or Double, the distance of a step in a diagonal
89 direction.
90 obstruction_characters -- An iterable of characters that obstruct movement.
91 '''
92
93 def __init__(self, area):
94 self.area = area # An instance of the Area() class.
95 self.c_dist = 100 # Could be 1.0, 10, 100, or 1000.
96 self.d_dist = 141 # Could be 1.4142135623730951, 14, 141, or 1414.
97 self.obstruction_characters = config.OBSTRUCTION_CHARACTERS
98 self._unobstruct_goals = None # Find a goal that is an obstruction.
99 self._cardinals = [( 0, -1, self.c_dist), ( 1, 0, self.c_dist),
100 ( 0, 1, self.c_dist), (-1, 0, self.c_dist)]
101 self._diagonals = [(-1, -1, self.d_dist), ( 1, -1, self.d_dist),
102 ( 1, 1, self.d_dist), (-1, 1, self.d_dist)]
103 self._directions = None # Cardinals, or cardinals + diagonals.
104 self._heuristic = None # The A-Star heuristic
105 self._x2, self._y2 = None, None # Used if the goal is a point.
106 self._tile, self._tiles = None, None # goal is a tile, tiles.
107 self._closed_set = set() # Evaluated tiles.
108 self._closed_set_coords = set() # Just the coords to speed up checks.
109 self._open_set = [] # Tiles to be evaluated.
110 self._open_set_coords = set() # Just the coords to speed up checks.
111 self._is_goal = None # Is this tile the goal?
112 self._print_path_info = False # Print info from retrace path.
113
114 def _is_goal_point(self, current_tile):
115 '''Is this the goal point?
116
117 current_tile -- List in [current + estimated distance, distance so far,
118 (current x, current y), (parent x, parent y)] format.
119
120 Return: Boolean. (True if the goal is found.)
121 '''
122
123 return current_tile[2] == (self._x2, self._y2)
124
125 def _is_goal_tile(self, current_tile):
126 '''Is this the goal tile?
127
128 current_tile -- List in [current + estimated distance, distance so far,
129 (current x, current y), (parent x, parent y)] format.
130
131
132 Return: Boolean. (True if the goal is found.)
133 '''
134
135 cur_x1, cur_y1 = current_tile[2]
136
137 return self.area.terrain[cur_y1][cur_x1] == self._tile
138
139 def _is_goal_iterable(self, current_tile):
140 '''Is this the goal as found in the iterable?
141
142 current_tile -- List in [current + estimated distance, distance so far,
143 (current x, current y), (parent x, parent y)] format.
144
145
146 Return: Boolean. (True if the goal is found.)
147 '''
148
149 cur_x1, cur_y1 = current_tile[2]
150
151 return self.area.terrain[cur_y1][cur_x1] in self._tiles
152
153 def _cardinal_heuristic(self, x1, y1, x2, y2):
154 '''Return the Manhattan distance.
155
156 x1, y1, x2, y2 -- Integers. Start and end coordinates.
157
158 Return: Int or Float. (The distance.)
159 '''
160
161 return (abs(x1 - x2) + abs(y1 - y2)) * self.c_dist
162
163 def _diagonal_heuristic(self, x1, y1, x2, y2):
164 '''Return the Chebyshev distance.
165
166 NOTE: Thanks /r/rogulikedev and RIngan.
167 NOTE 2: Use the c_dist distance as the d_dist may produce an
168 inadmissible heuristic as the path will likely not be strictly
169 diagonal.
170
171 x1, y1, x2, y2 -- Integers. Start and end coordinates.
172
173 Return: Int or Float. (The distance.)
174 '''
175
176 return (max([abs(x1 - x2), abs(y1 - y2)])) * self.c_dist
177
178 def _purge_private(self):
179 '''Purge Pathfinder()'s private values, usually before finding a new
180 path.
181
182 NOTE: self._heuristic = None preforms a Dijkstra search, set it to a
183 heuristic to use an A-Star search.
184 '''
185
186 self._x2, self._y2 = None, None
187 self._tile, self._tiles = None, None
188 self._heuristic = None
189 self._directions = None
190 self._open_set_coords = set()
191 self._open_set = []
192 self._closed_set = set()
193 self._closed_set_coords = set()
194 self._is_goal = None
195 self._unobstruct_goals = None
196
197 def _look_for_open(self, current_tile, best_path):
198 '''Add the eligible neighbours to open_set adjusting other tiles as
199 needed.
200
201 current_tile -- List in [current + estimated distance, distance so far,
202 (current x, current y), (parent x, parent y)] format.
203 best_path -- Boolean. 'True' to look for the best path. This is slower
204 as it involves modifying already processed tiles and possibly breaking
205 the heap invariant.
206 '''
207
208 x, y = current_tile[2]
209 current_dist = current_tile[1]
210
211 for direction in self._directions:
212 # NOTE: Implementing a '1' based movement cost system should be
213 # trivial in the following code.
214 x_mod, y_mod, step_dist = direction
215 new_x, new_y = x+x_mod, y+y_mod
216
217 # If it's not in bounds...
218 if 0 > new_x == self.area.width or 0 > new_y == self.area.height:
219
220 continue
221 else:
222 the_tile = self.area.terrain[new_y][new_x]
223
224 # Or is in the closed_set...
225 if (new_x, new_y) in self._closed_set_coords:
226
227 continue
228
229 # If not unobstructing goals and it hits an obstruction...
230 elif not self._unobstruct_goals and the_tile in\
231 self.obstruction_characters:
232
233 continue
234
235 # When looking for a goal find it even if it's an obstruction when
236 # unobstructing goals.
237 elif self._unobstruct_goals and the_tile in\
238 self.obstruction_characters:
239
240 if self._x2 and self._y2 and (
241 new_x, new_y) != (self._x2, self._y2):
242
243 continue
244 elif self._tile and self.area.terrain[
245 new_y][new_x] != self._tile:
246
247 continue
248 elif self._tiles and self.area.terrain[
249 new_y][new_x] not in self._tiles:
250
251 continue
252
253 # Update the distance travelled
254 dist = current_dist + step_dist
255 # Generate a heuristic distance for a goal that's a point.
256 # NOTE: if self._heuristic == None then do a Dijkstra search
257 # where the heuristic distance is just the distance traveled so
258 # far.
259 heuristic_distance = dist
260 if self._heuristic:
261 heuristic_distance += self._heuristic(new_x, new_y,
262 self._x2, self._y2)
263
264 # Not in the open_set:
265 if (new_x, new_y) not in self._open_set_coords:
266 self._open_set_coords.add((new_x, new_y))
267 heapq.heappush(self._open_set,
268 [heuristic_distance, # Heuristic distance
269 dist, # Distance traveled
270 (new_x, new_y), # (x, y)
271 (x, y)]) # (parent_x, parent_y)
272
273 # In the open_set and better. Avoid re-heapifying if the heap
274 # invariant is OK (as it generally is).
275 elif best_path:
276 for k, tile in enumerate(self._open_set):
277 if (new_x, new_y) == tile[1] and tile[3] > dist:
278
279 tile[0] = heuristic_distance
280 tile[2] = (x, y)
281 tile[3] = (dist)
282
283 parent = (k - 1) // 2
284 child_1 = (2 * k) + 1
285 child_2 = (2 * k) + 2
286
287 if parent in (0, -1):
288 parent_val = -1
289 else:
290 parent_val = self._open_set[parent][0]
291
292 if child_1 >= len(self._open_set):
293 child_1_val = float('inf')
294 else:
295 child_1_val = self._open_set[child_1][0]
296
297 if child_2 >= len(self._open_set):
298 child_2_val = float('inf')
299 else:
300 child_2_val = self._open_set[child_2][0]
301
302 # The heap invariant is OK if:
303 # parent < heuristic_distance < child_1 and child_2
304 if parent_val >= heuristic_distance >= min(
305 child_1_val, child_2_val):
306
307 heapq.heapify(self._open_set)
308 # print("Heap NOT OK.")
309 # else:
310 # print("Heap OK.")
311
312 break
313
314 def _retrace_path(self, current_tile):
315 '''Retrace a path to the start.
316
317 current_tile -- List in [current + estimated distance, distance so far,
318 (current x, current y), (parent x, parent y)] format.
319
320 Retrace a path to (x1, y1). A path includes the (x, y) of the goal /
321 target, but not that of the starting tile.
322
323 NOTE: This will retrace the path of any tile in the closed_set back to
324 the starting point, and may be useful for a number of purposes like
325 building Dijkstra maps for multiple consumers.
326
327 NOTE 2: Given python's recursion limit making this recursive is an iffy
328 proposition.
329
330 Return: deque(). (A deque of (x, y) Tuples representing the path.)
331 '''
332
333 parent = current_tile[3]
334 the_path = deque()
335 # The endpoint.
336 the_path.appendleft(current_tile[2])
337
338 while parent:
339 for tile in self._closed_set:
340 if tile[2] == parent:
341
342 parent = tile[3]
343 if parent:
344 # The parent
345 the_path.appendleft(tile[2])
346
347 break
348
349 if self._print_path_info:
350 print("\n\n==========")
351 print("\nCurrent:")
352 print(current_tile)
353 print("\nOpen Set Coordinates:")
354 print(self._open_set_coords)
355 print("\nOpen Set Length:")
356 print(len(self._open_set_coords))
357 print("\nClosed Set Coordinates:")
358 print(self._closed_set_coords)
359 print("\nClosed Set Length:")
360 print(len(self._closed_set_coords))
361 print("\nPath:")
362 print(the_path)
363 print("\nTile Steps:")
364 print(len(the_path))
365
366 return the_path
367
368 def _find_path(self, best_path, abort, goal_only):
369 '''Find a path.
370
371 best_path -- Boolean. 'True' to look for the best path. This is slower
372 as it involves modifying already processed tiles and possibly breaking
373 the heap invariant.
374 abort -- False, or Integer. If the len(self._closed_set) > abort stop
375 searching. This should stop any 'too slow' away searches.
376 goal_only -- Boolean. If True it will only return the (x, y, tile name)
377 of the goal, and not the path. Faster than retracing the path.
378
379 Return: deque, list, or None. (A deque of (x, y) Tuples, or a Tuple of
380 (x, y, tile name) if goal only == true, or None if no path is found.)
381 '''
382
383 while self._open_set:
384 current_tile = heapq.heappop(self._open_set)
385 self._open_set_coords.remove(current_tile[2])
386
387 # Yay, we found the goal!
388 if self._is_goal(current_tile) and not goal_only:
389 return self._retrace_path(current_tile)
390 elif self._is_goal(current_tile) and goal_only:
391 return (current_tile[2][0],
392 current_tile[2][1],
393 self.area.terrain[current_tile[2][1]]
394 [current_tile[2][0]])
395
396 # No goal, let's look for more tiles...
397 self._closed_set.add(tuple(current_tile))
398 self._closed_set_coords.add(current_tile[2])
399 # Abort search. Remember False == 0.
400 if len(self._closed_set_coords) > abort > 0:
401 return None
402 self._look_for_open(current_tile, best_path)
403
404 # Ooops, couldn't find a path!
405 return None
406
407 def find_point(self, x1, y1, x2, y2, use_diagonals=True, best_path=True,
408 abort=False):
409 '''Look for a specified point.
410
411 x1, y1, x2, y2 -- Integers. The start and end point.
412 use_diagonals -- Boolean. Path including diagonal directions. This is
413 slower as it has to check twice the tiles.
414 best_path -- Boolean. 'True' to look for the best path. This is slower
415 as it involves modifying already processed tiles and possibly breaking
416 the heap invariant. If set to 'False' paths are often somewhat more
417 organic, and can somewhat approximate a 'greedy best first' search.
418 abort -- False, or Integer. If the 'len(self._closed_set) > abort' stop
419 searching. This should stop any 'too slow' searches.
420
421 NOTE: This performs an A-Star search as it sets self._heuristic.
422
423 Return: deque or None. (A deque of (x, y) Tuples, or None if no path
424 is found.)
425 '''
426
427 self._purge_private()
428 self._x2 = x2
429 self._y2 = y2
430 self._unobstruct_goals = False
431
432 if use_diagonals:
433 self._heuristic = self._diagonal_heuristic
434 self._directions = set(self._cardinals + self._diagonals)
435 else:
436 self._heuristic = self._cardinal_heuristic
437 self._directions = set(self._cardinals)
438
439 self._is_goal = self._is_goal_point
440
441 self._open_set_coords.add((x1, y1))
442 heapq.heappush(self._open_set,
443 [0 + self._heuristic(x1, y1, x2, y2), # A-Star
444 0, # Distance traveled
445 (x1, y1), # (x, y)
446 None]) # (parent_x, parent_y)
447
448 return self._find_path(best_path, abort, False)
449
450 def is_point_findable(self, x1, y1, x2, y2, use_diagonals=True,
451 abort=False):
452 '''Can the pathfider find a given point?
453
454 NOTE: DO NOT USE THIS TO DETERMINE IF YOU SHOULD USE .find_point(), as
455 you will be doing a search to do a search. In that case just use
456 .find_point(). If you merely need to see if a tile is open please check
457 the Area().terrain data structure. If you need LOS cast a ray, or use
458 your FOV implementation. This is primarily useful for a 'blink' /
459 'teleport' that requires a valid path, but may not be directly seen.
460
461 x1, y1, x2, y2 -- Integers. The start and end point.
462 use_diagonals -- Boolean. Path including diagonal directions. This is
463 slower as it has to check twice the tiles.
464 abort -- False, or Integer. If the 'len(self._closed_set) > abort' stop
465 searching. This should stop any 'too slow' searches.
466
467 NOTE 2: This performs an A-Star search as it sets self._heuristic.
468
469 Return: Boolean. (True if the point is findable)
470 '''
471
472 self._purge_private()
473 self._x2 = x2
474 self._y2 = y2
475 self._unobstruct_goals = False
476
477 if use_diagonals:
478 self._heuristic = self._diagonal_heuristic
479 self._directions = set(self._cardinals + self._diagonals)
480 else:
481 self._heuristic = self._cardinal_heuristic
482 self._directions = set(self._cardinals)
483
484 self._is_goal = self._is_goal_point
485
486 self._open_set_coords.add((x1, y1))
487 heapq.heappush(self._open_set,
488 [0 + self._heuristic(x1, y1, x2, y2), # A-Star
489 0, # Distance traveled
490 (x1, y1), # (x, y)
491 None]) # (parent_x, parent_y)
492
493 found = self._find_path(False, abort, True)
494 if found:
495 return True
496 else:
497 return False
498
499 def find_tile(self, x1, y1, tile, use_diagonals=True, best_path=True,
500 abort=False):
501 '''Look for a specified tile, or tile in an iterable of tiles.
502
503 x1, y1 -- Integers. The start point.
504 tile -- String or Iterable. The tile, or an iterable of tiles, being
505 sought.
506 use_diagonals -- Boolean. Path including diagonal directions. This is
507 slower as it has to check twice the tiles.
508 best_path -- Boolean. 'True' to look for the best path. This is slower
509 as it involves modifying already processed tiles and possibly breaking
510 the heap invariant. If set to 'False' paths are often somewhat more
511 organic, and can somewhat approximate a 'greedy best first' search.
512 abort -- False, or Integer. If the 'len(self._closed_set) > abort' stop
513 searching. This should stop any 'too slow' searches.
514
515 NOTE: This performs an Dijkstra search as it doesn't set
516 self._heuristic.
517
518 Return: deque or None. (A deque of (x, y) Tuples, or None if no path
519 is found.)
520 '''
521
522 self._purge_private()
523
524 if type(tile) == str:
525 self._tile = tile
526 self._is_goal = self._is_goal_tile
527 else:
528 self._tiles = tile
529 self._is_goal = self._is_goal_iterable
530
531 self._unobstruct_goals = True
532
533 if use_diagonals:
534 self._directions = set(self._cardinals + self._diagonals)
535 else:
536 self._directions = set(self._cardinals)
537
538 self._open_set_coords.add((x1, y1))
539 heapq.heappush(self._open_set,
540 [0, # Dijkstra
541 0, # Distance traveled
542 (x1, y1), # (x, y)
543 None]) # (parent_x, parent_y)
544
545 return self._find_path(best_path, abort, False)
546
547 def nearest(self, x1, y1, tile, use_diagonals=True, abort=False):
548 '''Look for a specified tile, or tile in an iterable of tiles, and
549 return the location and name of that tile.
550
551 x1, y1 -- Integers. The start point.
552 tile -- String or Iterable. The tile, or an iterable of tiles, being
553 sought.
554 use_diagonals -- Boolean. Path including diagonal directions. This is
555 slower as it has to check twice the tiles.
556 abort -- False, or Integer. If the len(self._closed_set) > abort stop
557 searching. This should stop any 'too slow' away searches.
558
559 NOTE: This performs an Dijkstra search as it doesn't set
560 self._heuristic.
561
562 Return: Tuple or None. (A Tuple of (x, y, tile name), or None.)
563 '''
564
565 self._purge_private()
566
567 if type(tile) == str:
568 self._tile = tile
569 self._is_goal = self._is_goal_tile
570 else:
571 self._tiles = tile
572 self._is_goal = self._is_goal_iterable
573
574 self._unobstruct_goals = True
575
576 if use_diagonals:
577 self._directions = set(self._cardinals + self._diagonals)
578 else:
579 self._directions = set(self._cardinals)
580
581 self._open_set_coords.add((x1, y1))
582 heapq.heappush(self._open_set,
583 [0, # Dijkstra
584 0, # Distance traveled
585 (x1, y1), # (x, y)
586 None]) # (parent_x, parent_y)
587
588 return self._find_path(False, abort, True)
589
590
591if __name__ == '__main__':
592 '''Test the Pathfinder Class.'''
593
594 dun = ["#########################################################&#######",
595 "#.......#...#.........#...........#...............#.....#&#.-...#",
596 "#######.~...#........#..........#...................#...#&#.#...#",
597 "&&&&&&#.#...........#...........#~###################...###.#####",
598 "#######.#...#####.##............#...................#.....§.....#",
599 "#.......#...#&&#....##..........#...................#.....#####-#",
600 "#####+###...####....##.......#####################..#.....#.....#",
601 "#..##........................#&&#................#..#.....#.....#",
602 "#...##...........#########...####.............#..#..#.....#.....#",
603 "#....##..................#......#..###############..#.....#.....#",
604 "#.....##.................#.#....#..#...#...#...#....#.....#.....#",
605 "#......##.......#######..#.#....#....#...#...#...#..#.....#.##..#",
606 "#...............#&&&&&#..#.#....#####################.....#.##..#",
607 "#........#####..#&&&&&#..#.#.............#................##.#..#",
608 "#........#&&&#..#######....#.............#................#.##..#",
609 "#........#####.............#####.....#...#...#....###...####.#..#",
610 "#..............##########.............#..#..#.....#&#...#&#.##..#",
611 "#..............#........#..............#...#......###...####.#..#",
612 "#.##...###..####........#..#####........#.#...............#..#..#",
613 "#..............-........§..#........############..........####..#",
614 "####.#.........#........#..#........#....#.....#.########.......#",
615 "#.....#........##########..#.............#.......#&&#..###-####+#",
616 "#.....##...................#.............#.......#####.#&#......#",
617 "#.......#..................#.............#.......~.....#&#......#",
618 "########################################################&########"]
619
620 import pygame
621 from pygame.locals import *
622 import sys
623 import time
624 from fnmatch import filter
625
626 # Translate the character based map into Area().terrain tile names.
627 # Tile names are used to avoid character clashes in more complex maps.
628 rev = {}
629 tmp_terrain = []
630
631 for tile in config.TERRAIN_CHARACTERS:
632 tmp = config.TERRAIN_CHARACTERS[tile]
633 rev[tmp] = tile
634
635 for y in range(len(dun)):
636 tmp_terrain.append([])
637 for x in range(len(dun[y])):
638 tmp_terrain[y].append(rev[dun[y][x]])
639
640 test_area = Area()
641 test_area.terrain = tmp_terrain
642 test_area.width = len(tmp_terrain[0])
643 test_area.height = len(tmp_terrain)
644
645 # An instance of the pathfinder.
646 pathfinder = Pathfinder(test_area)
647
648 # Initialize Pygame.
649 pygame.display.init()
650 pygame.font.init()
651
652 clock = pygame.time.Clock()
653
654 pygame.display.set_caption("Pathfinding Test")
655
656 chosen_font = None
657 installed_fonts = pygame.font.get_fonts()
658
659 # Pick the first font from font_names, or the first font with *mono* in
660 # the name.
661 print("\nFONTS WITH MONO IN THE NAME:\n"
662 "============================")
663 print(filter(installed_fonts, "*mono*"))
664 first_mono = filter(installed_fonts, "*mono*")[0]
665
666 font_names = ["dejavusansmono",
667 "liberationmono",
668 "andalemono",
669 "lucidamono",
670 "notomono",
671 first_mono]
672
673 chosen_font = pygame.font.match_font(
674 [font_name for font_name in font_names if font_name in installed_fonts]
675 [0])
676
677 print("\nFONT:\n"
678 "=====")
679 print("Using font: " + chosen_font + '\n')
680
681 font_size = 18
682 font = pygame.font.Font(chosen_font, font_size)
683 font_w, font_h = font.size(" ")
684
685 font_size2 = 14
686 font2 = pygame.font.Font(chosen_font, font_size2)
687
688 n1, n2 = 8, 8
689 p1, p2 = 10, 10
690 default_fps = 60
691
692 R_color = 'red'
693 G_color = 'lime'
694 B_color = 'blue'
695 F_color = 'fuchsia'
696
697 pygame.key.set_repeat(250, 1000 // default_fps)
698
699 win = pygame.display.set_mode((test_area.width * font_w,
700 (test_area.height + 1) * font_h))
701
702 win.fill(config.COLORNAMES['black'])
703 txt1 = font.render("WSAD to move 'Ω', and ↑↓â†â†’ to move '@'.", True,
704 config.COLORNAMES['white'])
705 txt2 = font.render("Press an any key to begin...", True,
706 config.COLORNAMES['white'])
707 win.blit(txt1, (0, font_h * 5))
708 win.blit(txt2, (0, font_h * 7))
709
710 pygame.display.flip()
711
712 pad_h = test_area.height - 3
713 pad_w = test_area.width - 3
714
715 wait = True
716 while wait:
717 for event in pygame.event.get():
718 clock.tick(default_fps)
719 if event.type == KEYDOWN:
720 wait = False
721
722 win.fill(config.COLORNAMES['black'])
723
724 # The main loop.
725 while True:
726 # Set the FPS
727 clock.tick(default_fps)
728
729 for event in pygame.event.get():
730 if (event.type == QUIT or event.type == KEYDOWN and
731 event.key == K_ESCAPE):
732 pygame.quit()
733 sys.exit()
734
735 if event.type == KEYDOWN:
736 if event.key == K_UP:
737 if p2 > 1:
738 p2 -= 1
739 elif event.key == K_DOWN:
740 if p2 <= pad_h:
741 p2 += 1
742 elif event.key == K_LEFT:
743 if p1 > 1:
744 p1 -= 1
745 elif event.key == K_RIGHT:
746 if p1 <= pad_w:
747 p1 += 1
748 elif event.unicode == 'w':
749 if n2 > 1:
750 n2 -= 1
751 elif event.unicode == 's':
752 if n2 <= pad_h:
753 n2 += 1
754 elif event.unicode == 'a':
755 if n1 > 1:
756 n1 -= 1
757 elif event.unicode == 'd':
758 if n1 <= pad_w:
759 n1 += 1
760
761 # Calculate and (crudely) time the paths.
762 init_time = time.time()
763 point_path = pathfinder.find_point(p1, p2, n1, n2,
764 best_path=True,
765 use_diagonals=True,
766 abort=False)
767 point_time = time.time()
768 tile_path = pathfinder.find_tile(p1, p2, 'open door',
769 best_path=True,
770 use_diagonals=True,
771 abort=False)
772 tile_time = time.time()
773 tile_list_path = pathfinder.find_tile(p1, p2, ['closed door',
774 'closed secret door'],
775 best_path=True,
776 use_diagonals=True,
777 abort=False)
778 list_time = time.time()
779 nearest_tile = pathfinder.nearest(p1, p2, 'open secret door',
780 use_diagonals=True,
781 abort=False)
782 nearest_time = time.time()
783
784 win.fill(config.COLORNAMES['black'])
785
786 # Display the area on the given window.
787 for x1 in range(test_area.width):
788 for y1 in range(test_area.height):
789
790 char = None
791
792 if point_path and (x1, y1) in point_path:
793 color = R_color
794 elif tile_path and (x1, y1) in tile_path:
795 color = G_color
796 elif tile_list_path and (x1, y1) in tile_list_path:
797 color = B_color
798 elif nearest_tile and (x1, y1) ==\
799 (nearest_tile[0], nearest_tile[1]):
800 color = F_color
801 else:
802 color = config.TERRAIN_COLORS[
803 test_area.terrain[y1][x1]]
804
805 char = config.TERRAIN_CHARACTERS[
806 test_area.terrain[y1][x1]]
807
808 if x1 == p1 and y1 == p2:
809 color = 'yellow'
810 char = '@'
811
812 elif x1 == n1 and y1 == n2:
813 color = 'teal'
814 char = 'Ω'
815
816 if char:
817 char_surf = font.render(char, True,
818 config.COLORNAMES[color])
819 win.blit(char_surf, (x1 * font_w, y1 * font_h))
820
821 txt = (' |R Path in: ' +
822 str(round(point_time - init_time, 4)) +
823 ' |G Path in: ' +
824 str(round(tile_time - point_time, 4)) +
825 ' |B Path in: ' +
826 str(round(list_time - tile_time, 4)) +
827 ' |F Path in: ' +
828 str(round(nearest_time - list_time, 4)) +
829 ' |')
830
831 txt3 = font2.render(txt, True, config.COLORNAMES['white'])
832 win.blit(txt3, (0, font_h * test_area.height))
833
834 pygame.display.flip()