From 3ab9a2ef6f42f109e9b8460be2ea3ebfcc0af19b Mon Sep 17 00:00:00 2001
From: Christian Heller <c.heller@plomlompom.de>
Date: Thu, 12 Nov 2020 21:10:47 +0100
Subject: [PATCH] Optimize dijkstra mapping for volume calculation.

---
 plomrogue/commands.py | 34 ++++++++++++++++++++++------------
 plomrogue/mapping.py  | 16 ++++++++++++++++
 2 files changed, 38 insertions(+), 12 deletions(-)

diff --git a/plomrogue/commands.py b/plomrogue/commands.py
index 9c0111c..6c35665 100644
--- a/plomrogue/commands.py
+++ b/plomrogue/commands.py
@@ -15,7 +15,7 @@ def cmd_ALL(game, msg, connection_id):
         lowered_msg = ''
         for c in msg:
             c = c
-            while random.random() > volume * 4:
+            while random.random() > volume * 8:
                 if c.isupper():
                     c = c.lower()
                 elif c != '.':
@@ -29,25 +29,35 @@ def cmd_ALL(game, msg, connection_id):
     if not connection_id in game.sessions:
         raise GameError('need to be logged in for this')
     speaker = game.get_thing(game.sessions[connection_id], False)
-    dijkstra_map = Map(game.map_geometry.size)
-    n_max = 256
-    dijkstra_map.terrain = [n_max for i in range(dijkstra_map.size_i)]
-    dijkstra_map[speaker.position] = 0
+    n_max = 255
+    map_size = game.map.size_i
+    dijkstra_map = [n_max for i in range(game.map.size_i)]
+    dijkstra_map[game.map.get_position_index(speaker.position)] = 0
     shrunk = True
     while shrunk:
         shrunk = False
-        for pos in dijkstra_map:
-            if game.map[pos] == 'X':
+        for i in range(map_size):
+            if game.map.terrain[i] == 'X':
                 continue
-            neighbors = game.map_geometry.get_neighbors(pos)
+            neighbors = game.map_geometry.get_neighbors_i(i)
             for direction in [d for d in neighbors if neighbors[d]]:
-                yx = neighbors[direction]
-                if dijkstra_map[yx] < dijkstra_map[pos] - 1:
-                    dijkstra_map[pos] = dijkstra_map[yx] + 1
+                j = neighbors[direction]
+                if dijkstra_map[j] < dijkstra_map[i] - 1:
+                    dijkstra_map[i] = dijkstra_map[j] + 1
                     shrunk = True
+    #print('DEBUG')
+    #line_to_print = []
+    #x = 0
+    #for n in dijkstra_map:
+    #    line_to_print += ['%3s' % n]
+    #    x += 1
+    #    if x >= game.map.size.x:
+    #        x = 0
+    #        print(' '.join(line_to_print))
     for c_id in game.sessions:
         listener = game.get_thing(game.sessions[c_id], create_unfound=False)
-        volume = 1 / max(1, dijkstra_map[listener.position])
+        listener_vol = dijkstra_map[game.map.get_position_index(listener.position)]
+        volume = 1 / max(1, listener_vol)
         lowered_msg = lower_msg_by_volume(msg, volume)
         lowered_nick = lower_msg_by_volume(speaker.nickname, volume)
         game.io.send('CHAT ' +
diff --git a/plomrogue/mapping.py b/plomrogue/mapping.py
index 58809ef..01c10e8 100644
--- a/plomrogue/mapping.py
+++ b/plomrogue/mapping.py
@@ -20,6 +20,7 @@ class MapGeometry():
 
     def __init__(self, size):
         self.size = size
+        self.neighbors_i = {}
 
     def get_directions(self):
         directions = []
@@ -34,6 +35,21 @@ class MapGeometry():
             neighbors[direction] = self.move(pos, direction)
         return neighbors
 
+    def get_neighbors_i(self, i):
+        if i in self.neighbors_i:
+            return self.neighbors_i[i]
+        pos = YX(i // self.size.x, i % self.size.x)
+        neighbors_pos = self.get_neighbors(pos)
+        neighbors_i = {}
+        for direction in neighbors_pos:
+            pos = neighbors_pos[direction]
+            if pos is None:
+                neighbors_i[direction] = None
+            else:
+                neighbors_i[direction] = pos.y * self.size.x + pos.x
+        self.neighbors_i[i] = neighbors_i
+        return self.neighbors_i[i]
+
     def move(self, start_pos, direction):
         mover = getattr(self, 'move_' + direction)
         target = mover(start_pos)
-- 
2.30.2