There was two things to consider: how to arrange your turrets (your build), and which turrets to pick.
Can you have your computer produce the perfect layout?
Assuming that you assign a score for each area of the grid based on neighbor blocks and longest distance from start to finish, building a machine that maximizes the setup is NP-complete.
What about simply maximizing the overall vertical and horizontal distance that creeps have to follow? Still NP-complete.
Let's forget trying to build a deterministic algorithm and fall back on Monte Carlo instead.
The strategy is to randomly place blocks and retain the layouts with longest path from start to finish.
Here is the best layout found by my machine:

If you look at it closely, you'll see a resemblance with what a human would build
Here's the Python code:
graph.py
import sys import random import heapq class Graph: NODE_FREE = 0 NODE_OCCUPIED = -1 NODE_V_START = 10 NODE_V_END = 11 NODE_H_START = 20 NODE_H_END = 21 visited = [] def __init__(self, width, height): self.width = width self.height = height self.nnodes = width * height + 4 # grid + start and end points self.nedges = 0 self.nodes = [] self.edges = [] self.tower_pos = [] # list of nodes self.vstart = -1 self.vend = -1 self.hstart = -1 self.hend = -1 """ Add the nodes """ for _ in range(self.nnodes): self.nodes.append(self.NODE_FREE) row = [] for _ in range(self.nnodes): row.append(False) self.visited.append(False) self.edges.append(row) """ Set up the grid """ active_nodes = self.width * self.height for n in range(active_nodes): if n % self.width != 0: self.add_edge(n, n - 1) if n % self.width != self.width - 1: self.add_edge(n, n + 1) if n - self.width >= 0: self.add_edge(n, n - self.width) if n + self.width < active_nodes: self.add_edge(n, n + self.width) """ Define vertical and horizontal starting and ending nodes (4) Link start and end nodes to the entry and exit nodes (nodes #10-17, #529-536 and {208;234;260;286;312;338}, {233;259;285;311;337;363}) """ self.vstart = self.nnodes - 1 self.vend = self.nnodes - 2 self.hstart = self.nnodes - 3 self.hend = self.nnodes - 4 self.nodes[self.vstart] = self.NODE_V_START self.nodes[self.vend] = self.NODE_V_END self.nodes[self.hstart] = self.NODE_H_START self.nodes[self.hend] = self.NODE_H_END self.add_edge(self.vstart, 10) self.add_edge(self.vstart, 11) self.add_edge(self.vstart, 12) self.add_edge(self.vstart, 13) self.add_edge(self.vstart, 14) self.add_edge(self.vstart, 15) self.add_edge(self.vstart, 16) self.add_edge(self.vstart, 17) self.add_edge(self.vend, 529) self.add_edge(self.vend, 530) self.add_edge(self.vend, 531) self.add_edge(self.vend, 532) self.add_edge(self.vend, 533) self.add_edge(self.vend, 534) self.add_edge(self.vend, 535) self.add_edge(self.vend, 536) self.add_edge(self.hstart, 208) self.add_edge(self.hstart, 234) self.add_edge(self.hstart, 260) self.add_edge(self.hstart, 286) self.add_edge(self.hstart, 312) self.add_edge(self.hstart, 338) self.add_edge(self.hend, 233) self.add_edge(self.hend, 259) self.add_edge(self.hend, 285) self.add_edge(self.hend, 311) self.add_edge(self.hend, 337) self.add_edge(self.hend, 363) def display_vars(self): print self.nnodes, ": ", self.nodes print self.nedges, ": ", self.edges def display(self): for row in range(self.height): for col in range(self.width): if self.NODE_FREE == self.nodes[row * self.width + col]: print "-", else: print "X", print print def display_edges(self): for i in range(self.nnodes): print i, ": ", for j in range(self.nnodes): if True == self.edges[i][j]: print j, "(", self.nodes[j], ")", ", ", print def reset(self): self.tower_pos = [] for i in range(self.width * self.height): self.nodes[i] = self.NODE_FREE self.visited = [] for _ in range(self.nnodes): self.visited.append(False) """ Initialize the graph with turrets on the nodes given in the list @tower_pos """ def restore(self, tower_pos): self.reset() for i in tower_pos: self.place_tower_on_node(i) def add_node(self, val): self.nnodes += 1 self.nodes.append(val) row = [] for _ in range(self.max_nnodes): row.append(False) self.visited.append(False) self.edges.append(row) return self.nnodes-1 def add_edge(self, src, dst): self.edges[src][dst] = True self.edges[dst][src] = True self.nedges += 1 def del_edge(self, src, dst): self.edges[src][dst] = False self.edges[dst][src] = False self.nedges -= 1 def place_tower(self, row, col): """ Updates the graph to reflect the drawing of a tower """ if row < 0 or col < 0 or row >= self.height-1 or col >= self.width-1: return False node_num = row * self.width + col if self.nodes[node_num] != self.NODE_FREE or self.nodes[node_num + 1] != self.NODE_FREE or self.nodes[node_num + self.width] != self.NODE_FREE or self.nodes[node_num + self.width + 1] != self.NODE_FREE: return False self.nodes[node_num] = self.NODE_OCCUPIED self.nodes[node_num + 1] = self.NODE_OCCUPIED self.nodes[node_num + self.width] = self.NODE_OCCUPIED self.nodes[node_num + self.width + 1] = self.NODE_OCCUPIED self.tower_pos.append(node_num) return True def place_tower_on_node(self, node): """ Updates the graph to reflect the drawing of a tower """ row = node / self.width col = node % self.width if row < 0 or col < 0 or row >= self.height-1 or col >= self.width-1: return False if self.nodes[node] != self.NODE_FREE or self.nodes[node + 1] != self.NODE_FREE or self.nodes[node + self.width] != self.NODE_FREE or self.nodes[node + self.width + 1] != self.NODE_FREE: return False self.nodes[node] = self.NODE_OCCUPIED self.nodes[node + 1] = self.NODE_OCCUPIED self.nodes[node + self.width] = self.NODE_OCCUPIED self.nodes[node + self.width + 1] = self.NODE_OCCUPIED self.tower_pos.append(node) return True def dijkstra(self, start, end): q = [(0, start)] # Heap of (cost, path_head) visited = set() push, pop, add = heapq.heappush, heapq.heappop, visited.add while True: if 0 == len(q): return False (cost, v1) = pop(q) if v1 not in visited and self.nodes[v1] != self.NODE_OCCUPIED: add(v1) if v1 == end: return cost for v2 in range(self.nnodes): if True == self.edges[v1][v2]: if v2 not in visited: push(q, (cost + 1, v2)) def cc(self): visited = self.visited for count in range(self.nnodes): if (self.visited[count] == False): yield self.dfs(count) def dfs(self, start, target): return self.__run_dfs(start, target) def __run_dfs(self, i, target): self.visited[i] = True if i == target: return True for neighbor in range(self.nnodes): if True == self.edges[i][neighbor] and False == self.visited[neighbor]: self.__run_dfs(neighbor, target) return False
bestpath.py
import sys import random from dtd_graph import Graph def scramble(g): best_path = 0 nodes = [] while True: g.reset() for _ in range(68): node = random.randint(0, g.width * g.height) while False == g.place_tower_on_node(node): node = random.randint(0, g.width * g.height) vpath = g.dijkstra(g.vstart, g.vend) hpath = g.dijkstra(g.hstart, g.hend) if False == vpath or False == hpath: continue if best_path < vpath + hpath: best_path = vpath + hpath g.display() print vpath, hpath def run(): g_width = 26 g_height = 22 g = Graph(g_width, g_height) #g.display_edges() scramble(g) def main(): if len(sys.argv) != 1: print "usage: python", sys.argv[0], "< filename" return -1 else: run() if __name__ == '__main__': sys.exit(main())
No comments:
Post a Comment