What it needs:
- a map width and height.
- a list of enemies.
- a list of allies.
- Provide a threat graph for the entire map by:
- Seeding focuspoints across the map in an isometric pattern.
- Checking the threat level for a circle around each focuspoint.
- Then using this data to return a threat level for any point on the map by averaging from the nearby focuspoints. It uses an inversely weighted mean: the further the focuspoint is the less it counts.
- It automatically increases the coverage level in areas with units by creating intermediate focuspoints.
- It's written in python, to implement it you need to translate to Lua. I wrote it in python because I couldn't find an easy graphics system for Lua to be able to visualise it. I shall translate it to Lua soon.
- It doesn't delete intermediate focuspoints after units move out of the area so the list of points doesn't decrease again. In practical terms this shouldn't really be a serious disadvantage and it is better than creating all of the intermediate points right away because some of them may never be necessary.
[edit]Oh no! I do hope your screens are wider than mine, the lines are all messed up. Luckily your screens are very probably wider than mine...[/edit]
Code: Select all
#! /usr/bin/env python
#I don't know why I include the line above but I've seen it done and I've heard it has something to do with running under linux
#This is a python program to test some ideas I had for spring rts ai
#This version uses pygame so that you can view the algorithms in action
#place an ally by right-clicking
#left-clicking places an enemy
#this automatically adds them to the enemies and allies lists
#In the no-graphics version these lists must/can be created by the user
#It quits when the fifth ally is created.
#Joshua Msika
#started: 24/02/2010
#cleaned up and posted: 07/04/2010
#all positions are tuples in format (x,y)
class DGIS(object):
"""A dynamic geographical information system"""
#DGIS... I had grand ideas for this.
def __init__(self, mapwidth, mapheight, radius):
self.width = mapwidth
self.height = mapheight
self.radius = radius #the radius the focuspoints will use
self.points = [] #list of focuspoints
self.points = self.seedMap(self.width, self.height, self.radius)#see seedMap()
self.points0 = []#this is the original set of focuspoints and does not change
for f in self.points:
self.points0.append(f)
def seedMap(self,width,height,radius):
#this returns a list of focus points for the map. It guarantees coverage by 1 focuspoint, sometimes two.
points = []
for row in range(0,int(2*height/(3*radius))+2): #there is one row every 1.5 radii
for column in range(0,int(width/(3**0.5*radius)+2)): #one column every root(3) radii
position = (column*3**0.5*radius+row%2*3**0.5/2*radius, float(row)*3/2*radius)
if position[0]> width:
#this is messy but puts a line of focuspoints along the far edge of the map.
position = (width, float(row)*3/2*radius)
if position[1] >height:
position = (column*3**0.5*radius+row%2*3**0.5/2*radius, height) #Same comment
newpoint = Focuspoint(position,radius)
points.append(newpoint)
return points
def checkThreat(self,position):
#uses the focuspoint list to evaluate the threat at a certain location.
#It uses all points within radius and gives an inversely weighted average
#of their threat values according to distance.
d= 0
threat = 0
flag = True
for f in self.points:
if self.distance(f.position, position) <= f.radius:
distance = self.distance(f.position, position)
if distance == 0:
threat = f.threat #if the position is equal to a focuspoint's position then the threat is obvious.
flag = False
break
else:
threat += f.threat/distance#this line
d += 1/distance #and this one
if flag:
threat = threat/d #and this one compute the weighted average
return threat
def checkCoverage(self, position):
#returns the number of focus points that cover that position
coverage = 0
for f in self.points:
if self.distance(f.position, position) <= self.radius:
coverage += 1
return coverage
def update(self):
#updates the threat level for all focus points and adds extra focus points
#in areas with units
#this means that coverage in areas with units is always 3 and sometimes 4
uncovered = []
for a in allies:
coverage = self.checkCoverage(a.position)
if coverage < 3:
uncovered.append(a.position)
for e in enemies:
coverage = self.checkCoverage(e.position)
if coverage < 3:
uncovered.append(e.position)
#the following for-loop controls the creation of two new focuspoints equidistant from
#each other and from the two closest focuspoints of the original grid
for u in uncovered:
#two closest ORIGINAL focus points
a = (-10,0) #a will be to the left of u
b = (999999,0) #and b will be to the right of u
for f in self.points0:
if f.position[0]<u[0]:
if self.distance(f.position, u) < self.distance(a,u):
a = f.position #a is overwritten
if f.position[0]>=u[0]:
if self.distance(f.position, u) < self.distance(b,u):
b = f.position #b is overwritten
#the following mathematics can be derived from the euclidean distance formula and
#the point-slope form of the line that is equidistant from two points
x1 = a[0]
y1 = a[1]
x2 = b[0]
y2 = b[1]
if x1==x2:
slope = 0
elif y1==y2:
slope =False
else:
slope = float((x1-x2)/(y2-y1))
xmid = (x1+x2)*0.5
ymid = (y1+y2)*0.5
if slope:
newx = self.radius/2/(slope*slope+1)**0.5+xmid
newy = slope*(newx-xmid)+ymid
self.points.append(Focuspoint((newx,newy),self.radius))
newx = self.radius*-0.5/(slope*slope+1)**0.5+xmid
newy = slope*(newx-xmid)+ymid
self.points.append(Focuspoint((newx,newy),self.radius))
else:
#in case the points are vertically above each other
newx = xmid
newy = y1+0.5*self.radius
self.points.append(Focuspoint((newx,newy),self.radius))
newx = xmid
newy = y1-0.5*self.radius
self.points.append(Focuspoint((newx,newy),self.radius))
#updates all focuspoints:
for f in self.points:
f.checkThreat()
def distance(self,point1,point2):
#calculates the euclidean distance between two points
distance = ((point1[0]-point2[0])**2+(point1[1]-point2[1])**2)**0.5
return distance
class Unit(object):
"""a unit at a certain position, etc."""
#The Unit class is pretty much self-explanatory.
def __init__(self, position, target = None, threat = 1):
self.position = position #a unit's current position
self.target = target #a unit's target position
self.threat = threat #a unit's firepower or ability to harm
self.waypoint = self.position #the position the unit is trying to go to.
class Focuspoint(object):
#The points used by DGIS to graph the threat level across the whole map
def __init__(self, position, radius, threat=1):
self.position = position
self.radius = radius #the radius in which units are considered for checkThreat()
self.threat = threat #the threat level at this point
def checkThreat(self):
#checks threat within a certain radius of positions. This method could easily be improved/expanded
threat = 0
for a in allies:
distance = DGIS.distance(self.position, a.position)
if distance < self.radius:
threat -= a.threat #subtracts an ally's firepower
for e in enemies:
distance = DGIS.distance(self.position, e.position)
if distance < self.radius:
threat += e.threat #adds an enemy's firepower
self.threat = threat
return self.threat
#The following code allows viewing of the algorithm in action using pygame:
import pygame
pygame.init()
pygame.display.init()
#Let's define some colours
RED = (255,0,0)
YELLOW = (255,255,0)
GREEN = (0,255,0)
CYAN = (0,255,255)
BLUE = (0,0,255)
PURPLE = (255,0,255)
WHITE = (255,255,255)
BLACK = (0,0,0)
def draw(res):
for i in range(WIDTH/res):
for j in range(HEIGHT/res):
threat = DGIS.checkThreat(((i+0.5)*res,(j+0.5)*res))
colour = (0+2**threat*32,0+2**threat*32,0+2**threat*32)
if 0+2**threat*32>255:
colour = (255,255,255)
pygame.draw.rect(screen,colour,((i*res,j*res),(i*res+res,j*res+res)))
for f in DGIS.points:
position = (int(f.position[0]), int(f.position[1]))
pygame.draw.circle(screen,BLUE,position,2)
for a in allies:
pygame.draw.circle(screen,GREEN,a.position,2)
for e in enemies:
pygame.draw.circle(screen,RED,e.position,2)
return None
def mainloop():
event = pygame.event.poll()
screen.fill(BLACK)
if event.type == 5 and event.dict['button']==1:
newally = Unit(event.dict['pos'])
allies.append(newally)
elif event.type == 5 and event.dict['button']==3:
newenemy = Unit(event.dict['pos'])
enemies.append(newenemy)
elif event.type == 4:
position = event.dict['pos']
caption = "Position: "+ str(position)+ "Threat: "+ str(DGIS.checkThreat(position))
pygame.display.set_caption(caption)
DGIS.update()
draw(15)
pygame.display.flip()
return None
allies = []#this list
enemies = []#and this one are essential for DGIS to work
WIDTH = 800
HEIGHT = 500
DGIS = DGIS(WIDTH,HEIGHT, 50)
screen = pygame.display.set_mode((WIDTH,HEIGHT))
while len(allies) < 8:
mainloop()
pygame.display.quit()
pygame.quit()
