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