From 2856c56c3b06c6d62b21bea9f120d479610e7ec2 Mon Sep 17 00:00:00 2001
From: Neil <neil@dip.sun.ac.za>
Date: Thu, 18 Apr 2013 21:36:30 +0200
Subject: [PATCH] 'Better' AI

---
 erdslangetjie/player.py | 49 +++++++++++++++++++++++++++++------------
 1 file changed, 35 insertions(+), 14 deletions(-)

diff --git a/erdslangetjie/player.py b/erdslangetjie/player.py
index 7c80263..b6b4abf 100644
--- a/erdslangetjie/player.py
+++ b/erdslangetjie/player.py
@@ -43,8 +43,8 @@ class Nemesis(FigureSprite):
         super(Nemesis, self).__init__()
         self.sprite = load_image('sprites/nemesis.png')
         self.reset_pos()
-        self.deadends = []
-        self.been = []
+        self._deadends = set([])
+        self._been = {}
 
     def move(self, level, player_pos):
         if not self.on_board():
@@ -52,7 +52,7 @@ class Nemesis(FigureSprite):
             self.pos = (self.pos[0] + 1, self.pos[1])
             if self.on_board():
                 self.pos = level.enter_pos
-            return False
+            return
         # AI goes here
         # First, if we're standing next to a gate, we attack it
         neighbours = [(self.pos[0] + 1, self.pos[1]),
@@ -62,22 +62,43 @@ class Nemesis(FigureSprite):
         for cand in neighbours:
             if level.is_gate(cand) and level.blocked(cand):
                 level.damage_gate(cand)
-                return True
-        steps = 0
-        self.been.append(self.pos)
+                return
+        # check for dead-ends
+        if self._in_dead_end(level):
+            self._deadends.add(self.pos)
+        self._been.setdefault(self.pos, 0)
+        mindist = 999999
+        best_pos = None
         for direction in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
             new_pos = (self.pos[0] + direction[0], self.pos[1] + direction[1])
-            if self.can_move(direction, level) and new_pos not in self.been:
-                self.pos = new_pos
-                self.been.append(new_pos)
-                steps += 1
-                break
-        if steps == 0:
-            self.been = []
-        return True
+            if new_pos in self._deadends:
+                continue
+            if self.can_move(direction, level):
+                # We weigh stuff by the number of times we've stepped there, to
+                # avoid certain types of loop
+                dist = (level.calc_dist(new_pos, player_pos)
+                        + self._been.get(new_pos, 0))
+                if dist < mindist:
+                    mindist = dist
+                    best_pos = new_pos
+        if best_pos:
+            self._been[self.pos] += 1
+            self.pos = best_pos
 
     def reset_pos(self):
         self.pos = (-10, 0)
+        self._deadends = set([])
+        self._been = {}
 
     def on_board(self):
         return self.pos[0] >= 0
+
+    def _in_dead_end(self, level):
+        # Check if this is a dead end
+        blocked = 0
+        for direction in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
+            new_pos = (self.pos[0] + direction[0], self.pos[1] + direction[1])
+            if level.is_wall(new_pos) or new_pos in self._deadends:
+                blocked += 1
+        # A dead end has only 1 exit, and recurse back from there
+        return blocked >= 3
-- 
2.34.1