Commits

Anonymous committed 2182f3f

implemented real A* path planning.

  • Participants
  • Parent commits 78e4122

Comments (0)

Files changed (2)

File hexbattle_logic.py

         self.num_rats = 10
         self.num_goblins = 7
         
-    
     def are_enemies(self, unit, other):
         """Check if the given units are enemies."""
         return unit.team is None or other.team is None or not unit.team == other.team
                 units.append(other)
         return units
     
+    def free_hex_around(self, x, y):
+        """Return the units around the hexfield."""
+        hexes = []
+        for hex_x, hex_y in self.hex_vectors[1:]:
+            pos = hex_x + x, hex_y + y
+            other = self.hexmap.get(pos, None)
+            if other is None: 
+                hexes.append(pos)
+        return hexes
+    
     def enemies_around(self, unit):
         """Return the enemies which are on hexes touching the hex of the unit (hexfield).
         
             char.show()
             char.attack = 18
             self.chars.append(char)
-    
+
     def setup_step(self, dt=0):
         """setup the level."""
         # if we do not have characters yet, we add all of them.

File hexbattle_units.py

         """Get all hexfields to which the Charakter could move.
 
         TODO: Move method into model, as it deals with relationship between units.
+        
+        FIXME: Some 
         """
-        targets = []
+        targets = set()
         # basic optimization: only check a hex-„square“ around the blob.
         for x in range(-self.max_move, self.max_move+1):
             for y in range(-self.max_move, self.max_move+1):
+                pos = (self.hex_x + x, self.hex_y + y)
+                if pos in targets:
+                    continue
                 z = - (x+y)
                 dist = 0.5*(abs(x)+abs(y)+abs(z))
                 if dist <= self.max_move:
-                    pos = (self.hex_x + x, self.hex_y + y)
                     # don’t list those places which are already taken.
                     hexunit = self.hexmap.get(pos, None)
-                    if hexunit is None or hexunit is self: 
-                        targets.append(pos)
-        return targets
+                    if hexunit is self:
+                        targets.add(pos)
+                    if hexunit is None: 
+                        path = self.path_to(pos)
+                        if not path: # no path to target
+                            continue
+                        for pos in path[:self.max_move]:
+                            targets.add(pos)
+                        # if we can reach the target, add it
+                        pos_is_reachable = len(path) < self.max_move
+                        if pos_is_reachable:
+                            targets.add(pos)
+        
+        return list(targets)
+
+    def path_to(self, goal):
+        """Find the cheapest path towards the goal hex.
+
+        TODO: interleaf with movement targets to reduce the cost.
+        
+        :return: the list of hexes to traverse or None (if no path could be found).
+        """
+        def twopos2fourhex(pos1, pos2):
+            return pos1[0], pos1[1], pos2[0], pos2[1]
+        def free_neighbor_nodes(pos):
+            return [(h[0] + pos[0], h[1] + pos[1]) for h in hex_vectors[1:] if self.hexmap.get((h[0] + pos[0], h[1] + pos[1]), None) is None]
+        def dist_heuristic(pos1, pos2):
+            """The estimated distance between two nodes."""
+            return hexgrid_distance(*twopos2fourhex(pos1, pos2))
+        #: TODO: replace by weighted distances which allow different terrains to have different real costs between neighboring nodes.
+        dist = dist_heuristic
+        def reconstruct(previous, current):
+            if current in previous:
+                p = reconstruct(previous, previous[current])
+                return p + (current, )
+            return (current, )
+        # TODO: implement path planning
+        closed = set()
+        start = (self.hex_x, self.hex_y)
+        # TODO: use a heapq
+        openset = set([start])
+        #: node before the current one
+        previous = {}
+        #: Known shortest distance to each node
+        g = {}
+        g[start] = 0
+        #: Estimate of the distance between two nodes
+        h = {}
+        h[start] = dist(start, goal)
+        #: Combined distance
+        f = {}
+        f[start] = g[start] + h[start]
+        def fval(pos):
+            return f[pos]
+
+        while openset:
+            current = sorted(openset, key=fval)[0]
+            if current == goal:
+                return reconstruct(previous, previous[goal])
+            openset.remove(current)
+            closed.add(current)
+            for neighbor in free_neighbor_nodes(current):
+                if neighbor in closed: continue
+                g_tentative = g[current] + dist(current, neighbor)
+                if not neighbor in openset:
+                    openset.add(neighbor)
+                    h[neighbor] = dist_heuristic(neighbor, goal)
+                    tentative_is_better = True
+                elif g_tentative < g[neighbor]:
+                    tentative_is_better = True
+                else:
+                    tentative_is_better = False
+                
+                if tentative_is_better:
+                    previous[neighbor] = current
+                    g[neighbor] = g_tentative
+                    f[neighbor] = g[neighbor] + h[neighbor]
+        
+        return None # explicit fail
 
     def _guess_damage_against(self, target):
         """Guess the damage we will do against a given target."""
 
     def guess_damage_at(self, hexpos):
         """Guess the damage we can do on the given hexfield."""
-        enemies_around = [u for u in self.model.units_around_hex(hexpos[0], hexpos[1]) if self.model.are_enemies(self, u)]
+        enemies_around = self.model.enemies_around(self)
         if not enemies_around:
             return 0
         my_malus = 3*len(enemies_around) - 3