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