A-Star Path Finding

A-Star Path Finding
astar_pathfinding.py
  1"""
  2A-Star Path-finding
  3
  4.. note:: This uses features from the upcoming version 2.4. The API for these
  5          functions may still change. To use, you will need to install one of the
  6          pre-release packages, or install via GitHub.
  7
  8Artwork from http://kenney.nl
  9
 10If Python and Arcade are installed, this example can be run from the command line with:
 11python -m arcade.examples.astar_pathfinding
 12"""
 13
 14import arcade
 15import os
 16import random
 17
 18SPRITE_IMAGE_SIZE = 128
 19SPRITE_SCALING = 0.25
 20SPRITE_SIZE = SPRITE_IMAGE_SIZE * SPRITE_SCALING
 21
 22SCREEN_WIDTH = 800
 23SCREEN_HEIGHT = 600
 24SCREEN_TITLE = "A-Star Path-finding"
 25
 26MOVEMENT_SPEED = 5
 27
 28VIEWPORT_MARGIN = 100
 29
 30
 31class MyGame(arcade.Window):
 32    """
 33    Main application class.
 34    """
 35
 36    def __init__(self, width, height, title):
 37        """
 38        Initializer
 39        """
 40
 41        # Call the parent class initializer
 42        super().__init__(width, height, title)
 43
 44        # Set the working directory (where we expect to find files) to the same
 45        # directory this .py file is in. You can leave this out of your own
 46        # code, but it is needed to easily run the examples using "python -m"
 47        # as mentioned at the top of this program.
 48        file_path = os.path.dirname(os.path.abspath(__file__))
 49        os.chdir(file_path)
 50
 51        # Variables that will hold sprite lists
 52        self.player_list = None
 53        self.wall_list = None
 54        self.enemy_list = None
 55
 56        # Set up the player info
 57        self.player = None
 58
 59        # Track the current state of what key is pressed
 60        self.left_pressed = False
 61        self.right_pressed = False
 62        self.up_pressed = False
 63        self.down_pressed = False
 64
 65        self.physics_engine = None
 66
 67        # --- Related to paths
 68        # List of points that makes up a path between two points
 69        self.path = None
 70        # List of points we checked to see if there is a barrier there
 71        self.barrier_list = None
 72
 73        # Used in scrolling
 74        self.view_bottom = 0
 75        self.view_left = 0
 76
 77        # Set the background color
 78        arcade.set_background_color(arcade.color.AMAZON)
 79
 80    def setup(self):
 81        """ Set up the game and initialize the variables. """
 82
 83        # Sprite lists
 84        self.player_list = arcade.SpriteList()
 85        self.wall_list = arcade.SpriteList(use_spatial_hash=True, spatial_hash_cell_size=128)
 86        self.enemy_list = arcade.SpriteList()
 87
 88        # Set up the player
 89        self.player = arcade.Sprite(":resources:images/animated_characters/female_person/femalePerson_idle.png", SPRITE_SCALING)
 90        self.player.center_x = SPRITE_SIZE * 5
 91        self.player.center_y = SPRITE_SIZE * 1
 92        self.player_list.append(self.player)
 93
 94        # Set enemies
 95        enemy = arcade.Sprite(":resources:images/animated_characters/zombie/zombie_idle.png", SPRITE_SCALING)
 96        enemy.center_x = SPRITE_SIZE * 4
 97        enemy.center_y = SPRITE_SIZE * 7
 98        self.enemy_list.append(enemy)
 99
100        spacing = SPRITE_SIZE * 3
101        for column in range(10):
102            for row in range(15):
103                sprite = arcade.Sprite(":resources:images/tiles/grassCenter.png", SPRITE_SCALING)
104
105                x = (column + 1) * spacing
106                y = (row + 1) * sprite.height
107
108                sprite.center_x = x
109                sprite.center_y = y
110                if random.randrange(100) > 30:
111                    self.wall_list.append(sprite)
112
113        self.physics_engine = arcade.PhysicsEngineSimple(self.player,
114                                                         self.wall_list)
115
116        # --- Path related
117        # This variable holds the travel-path. We keep it as an attribute so
118        # we can calculate it in on_update, and draw it in on_draw.
119        self.path = None
120        # Grid size for calculations. The smaller the grid, the longer the time
121        # for calculations. Make sure the grid aligns with the sprite wall grid,
122        # or some openings might be missed.
123        grid_size = SPRITE_SIZE
124
125        # Calculate the playing field size. We can't generate paths outside of
126        # this.
127        playing_field_left_boundary = -SPRITE_SIZE * 2
128        playing_field_right_boundary = SPRITE_SIZE * 35
129        playing_field_top_boundary = SPRITE_SIZE * 17
130        playing_field_bottom_boundary = -SPRITE_SIZE * 2
131
132        # This calculates a list of barriers. By calculating it here in the
133        # init, we are assuming this list does not change. In this example,
134        # our walls don't move, so that is ok. If we want moving barriers (such as
135        # moving platforms or enemies) we need to recalculate. This can be an
136        # time-intensive process depending on the playing field size and grid
137        # resolution.
138
139        # Note: If the enemy sprites are the same size, we only need to calculate
140        # one of these. We do NOT need a different one for each enemy. The sprite
141        # is just used for a size calculation.
142        self.barrier_list = arcade.AStarBarrierList(enemy,
143                                                    self.wall_list,
144                                                    grid_size,
145                                                    playing_field_left_boundary,
146                                                    playing_field_right_boundary,
147                                                    playing_field_bottom_boundary,
148                                                    playing_field_top_boundary)
149
150    def on_draw(self):
151        """
152        Render the screen.
153        """
154        try:
155            # This command has to happen before we start drawing
156            arcade.start_render()
157
158            # Draw all the sprites.
159            self.player_list.draw()
160            self.wall_list.draw()
161            self.enemy_list.draw()
162
163            if self.path:
164                arcade.draw_line_strip(self.path, arcade.color.BLUE, 2)
165
166        except Exception:
167
168            import traceback
169            traceback.print_exc()
170
171    def on_update(self, delta_time):
172        """ Movement and game logic """
173
174        try:
175            # Calculate speed based on the keys pressed
176            self.player.change_x = 0
177            self.player.change_y = 0
178
179            if self.up_pressed and not self.down_pressed:
180                self.player.change_y = MOVEMENT_SPEED
181            elif self.down_pressed and not self.up_pressed:
182                self.player.change_y = -MOVEMENT_SPEED
183            if self.left_pressed and not self.right_pressed:
184                self.player.change_x = -MOVEMENT_SPEED
185            elif self.right_pressed and not self.left_pressed:
186                self.player.change_x = MOVEMENT_SPEED
187
188            # Update the character
189            self.physics_engine.update()
190
191            # Calculate a path to the player
192            enemy = self.enemy_list[0]
193            # Set to True if we can move diagonally. Note that diagnonal movement
194            # might cause the enemy to clip corners.
195            self.path = arcade.astar_calculate_path(enemy.position,
196                                                    self.player.position,
197                                                    self.barrier_list,
198                                                    diagonal_movement=False)
199                # print(self.path,"->", self.player.position)
200
201            # --- Manage Scrolling ---
202
203            # Keep track of if we changed the boundary. We don't want to call the
204            # set_viewport command if we didn't change the view port.
205            changed = False
206
207            # Scroll left
208            left_boundary = self.view_left + VIEWPORT_MARGIN
209            if self.player.left < left_boundary:
210                self.view_left -= left_boundary - self.player.left
211                changed = True
212
213            # Scroll right
214            right_boundary = self.view_left + SCREEN_WIDTH - VIEWPORT_MARGIN
215            if self.player.right > right_boundary:
216                self.view_left += self.player.right - right_boundary
217                changed = True
218
219            # Scroll up
220            top_boundary = self.view_bottom + SCREEN_HEIGHT - VIEWPORT_MARGIN
221            if self.player.top > top_boundary:
222                self.view_bottom += self.player.top - top_boundary
223                changed = True
224
225            # Scroll down
226            bottom_boundary = self.view_bottom + VIEWPORT_MARGIN
227            if self.player.bottom < bottom_boundary:
228                self.view_bottom -= bottom_boundary - self.player.bottom
229                changed = True
230
231            # Make sure our boundaries are integer values. While the view port does
232            # support floating point numbers, for this application we want every pixel
233            # in the view port to map directly onto a pixel on the screen. We don't want
234            # any rounding errors.
235            self.view_left = int(self.view_left)
236            self.view_bottom = int(self.view_bottom)
237
238            # If we changed the boundary values, update the view port to match
239            if changed:
240                arcade.set_viewport(self.view_left,
241                                    SCREEN_WIDTH + self.view_left,
242                                    self.view_bottom,
243                                    SCREEN_HEIGHT + self.view_bottom)
244
245        except Exception:
246            import traceback
247            traceback.print_exc()
248
249    def on_key_press(self, key, modifiers):
250        """Called whenever a key is pressed. """
251
252        if key == arcade.key.UP:
253            self.up_pressed = True
254        elif key == arcade.key.DOWN:
255            self.down_pressed = True
256        elif key == arcade.key.LEFT:
257            self.left_pressed = True
258        elif key == arcade.key.RIGHT:
259            self.right_pressed = True
260
261    def on_key_release(self, key, modifiers):
262        """Called when the user releases a key. """
263
264        if key == arcade.key.UP:
265            self.up_pressed = False
266        elif key == arcade.key.DOWN:
267            self.down_pressed = False
268        elif key == arcade.key.LEFT:
269            self.left_pressed = False
270        elif key == arcade.key.RIGHT:
271            self.right_pressed = False
272
273
274def main():
275    """ Main method """
276    window = MyGame(SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_TITLE)
277    window.setup()
278    arcade.run()
279
280
281if __name__ == "__main__":
282    main()