A-Star Path Finding#

A-Star Path Finding

Explanation#

A-star path finding can be used to find a way to go from one spot to another around barriers. This example just draws the path, based on the coordinates returned. If you want the enemy to follow that path, see Sprites That Follow a Path.

Source#

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