[[nichteuklidische_geometrie|← Back to project page]]
====== Sourcecode ======
Download the release version here:\\
{{:ss20:neg-world-engine.zip}}
Or download the newest version from the Git repository:\\
[[https://gitlab.tubit.tu-berlin.de/srather/NEG-World-Engine.git]]
==== Folder Structure: ====
**[[neg_sourcecode|Root]]:** [[neg_sourcecode#readme|README]], [[neg_sourcecode#main|main]]
* **[[neg_datatypes|Datatypes]]:** [[neg_datatypes#vector|Vector]], [[neg_datatypes#matrix|Matrix]]
* **[[neg_drawables|Drawables]]:** [[neg_drawables#drawable|drawable]], [[neg_drawables#ray|Ray]], [[neg_drawables#polygon|Polygon]], [[neg_drawables#floor|Floor]], [[neg_drawables#portal|Portal]]
* **[[neg_utility|Utility]]:** [[neg_utility#colors|colors]], [[neg_utility#generate|generate]], [[neg_utility#draw|draw]]
===== Objects =====
----
==== drawable ====
import colors
from vector import *
class drawable(list):
"""
Abstract superclass for all objects drawable on canvas.
A drawable is a list of points ('Vector') with a 'color' attribute.
"""
def __init__(self, *points, color=colors.BLACK):
"""
Overrides '__init__' method of 'list' class.
Will only accept point-like objects and adds 'color' attribute.
"""
list.__init__(self)
for point in points:
drawable.append(self, point)
self.color = color
def append(self, item):
"""
Overrides 'append' method of 'list' class.
Will only accept point-like objects.
"""
try:
list.append(self, Vector(*item))
except:
raise TypeError(f"Expected vector/point, but got {item.__class__.__name__}")
def __str__(self):
"""
Override '__str__' method of 'list' class.
Return string with classname, points in 'self' and additional attributes.
"""
return f"{self.__class__.__name__}({list.__repr__(self)[1:-1]}) with {self.__dict__.__repr__()[1:-1].replace(':', ' =').replace(' ', '')}"
def __repr__(self):
"""
Override '__repr__' method of 'list' class.
Return string with classname, points in 'self' and additional attributes.
"""
return f"{self.__class__.__name__}({list.__repr__(self)[1:-1]}, {self.__dict__.__repr__()[1:-1].replace(':', ' =').replace(' ', '')})"
def draw(self, screen, offset):
"""Abstract method to draw 'self' on 'screen'."""
raise NotImplementedError
def draw_shadow(self, screen, offset, source, color=(31,31,31)):
"""Abstract method to draw a shadow of 'self' on 'screen'."""
raise NotImplementedError
def dist_to(self, source):
"""Abstract method to calculate the distance to the player ('source')."""
raise NotImplementedError
def cut(self, source, portal):
"""Abstract method to cut 'self' to fit in the portal view."""
raise NotImplementedError
[[#top|↑ Back to top]]
----
==== Ray ====
import pygame.gfxdraw
import colors
from drawable import *
from matrix import *
class Ray(drawable):
"""
Ray class as drawable object for visual debug.
A Ray has a starting point and a direction vector.
"""
def __init__(self, start, dir, color=colors.BRIGHT_RED):
"""Initilise 'self' with standard color 'BRIGHT_RED'."""
drawable.__init__(self, start, dir, color=color)
def __getattr__(self, attr):
"""
Return 'self[0]' and 'self[1]' as attribute 'start' and 'dir'.
"""
if attr == 'start':
return self[0]
if attr == 'dir':
return self[1]
def point_at(self, value):
"""
Return the point 'self.start + value * self.dir'.
"""
if type(value) in (int, float):
return self.start + value * self.dir
raise TypeError(f"Expected int or float, but {value.__class__.__name__} found")
def value_at(self, point):
"""
Return the value with 'point_at(value) == point'.
"""
if type(point) is Vector:
if self.dir.multiple_of(point - self.start):
value = (point - self.start) / self.dir
if value is not None:
return value
# hotfix
h = (point - self.start).dot(self.dir) / self.dir.dot(self.dir)
print(f"Warning: returned nearest value for 'value_at' of point {((point - self.start) - h * self.dir).length()} off the ray)")
return h
raise TypeError(f"Expected Vector, but {point.__class__.__name__} found")
def offscreen(self, screen, offset):
"""
Return a point of the ray that is not on the rect 'screen'.
This assumes all rays go away from the 'screen' center.
"""
if not self.dir: # == 0
return self.start
x, y = float('inf'), float('inf')
if self.dir.x > 0:
x = (offset.x + screen.get_rect()[2] / 2 - self.start.x) / self.dir.x
elif self.dir.x < 0:
x = (offset.x - screen.get_rect()[2] / 2 - self.start.x) / self.dir.x
if self.dir.y > 0:
y = (offset.y + screen.get_rect()[3] / 2 - self.start.y) / self.dir.y
elif self.dir.y < 0:
y = (offset.y - screen.get_rect()[3] / 2 - self.start.y) / self.dir.y
return self.point_at(max(0, min(x, y)))
def intersect(self, other):
"""
Return list of intersections sorted by distance to 'self.start'.
"""
if self.dir.length() == 0:
return []
# point
if isinstance(other, Vector):
if self.dir.multiple_of(other - self.start): # point on self
if self.value_at(other) is not None:
return [other]
return []
if isinstance(other, drawable):
if type(other) is Ray:
if self.dir.multiple_of(other.dir): # linear depentant
return self.intersect(other.start)
if self.dir.x == 0:
# switch vectors for gauss algorithm
return other.intersect(self)
matrix = [
[self.dir.x, -other.dir.x, other.start.x - self.start.x],
[self.dir.y, -other.dir.y, other.start.y - self.start.y],
]
# gauss algorithm
matrix[0][1] /= matrix[0][0]
matrix[0][2] /= matrix[0][0]
matrix[1][1] -= matrix[1][0] * matrix[0][1]
matrix[1][2] -= matrix[1][0] * matrix[0][2]
matrix[1][2] /= matrix[1][1]
matrix[0][2] -= matrix[0][1] * matrix[1][2]
if matrix[0][2] >= 0 and matrix[1][2] >= 0:
return [self.point_at(matrix[0][2])]
return []
raise NotImplementedError # for other drawables
raise TypeError(f"Expected drawable objects or vector, but '{other.__class__.__name__}' found")
def draw(self, screen, offset):
"""
Draw 'self' as an infinite ray on 'screen'.
"""
ray = Ray(self.start, self.offscreen(screen, offset))
# calculate real position on screen
rect = Vector(*screen.get_rect()[2:])
for i, _ in enumerate(ray):
ray[i] = round(ray[i] - offset + rect / 2)
if ray.dir: # != 0
pygame.draw.aaline(screen, self.color, ray[0], ray[1])
[[#top|↑ Back to top]]
----
==== Polygon ====
import colors
from drawable import *
from ray import *
class Polygon(drawable):
"""
Polygon class as 'drawable' objects.
Implements functionality of abstract drawable class.
"""
def __init__(self, *points, color=colors.BLACK):
"""Initilise 'self' with standard color 'BLACK'."""
drawable.__init__(self, *points, color=color)
def draw(self, screen, offset):
"""
Draw 'self' as a polygon on 'screen'.
"""
if not self: # empty
return
polygon = self.copy()
# calculate real position on screen
rect = Vector(*screen.get_rect()[2:])
for i, _ in enumerate(polygon):
polygon[i] = round(polygon[i] - offset + rect / 2)
if polygon[i].length2() > 30000: # hotfix
return
# point
if len(polygon) == 1:
pygame.gfxdraw.pixel(screen, *polygon[0], self.color)
# line
elif len(polygon) == 2:
pygame.draw.aaline(screen, self.color, polygon[0], polygon[1])
# polygon
else:
pygame.gfxdraw.aapolygon(screen, polygon, self.color)
pygame.gfxdraw.filled_polygon(screen, polygon, self.color)
def draw_shadow(self, screen, offset, source, color=colors.DARK_GRAY):
"""
Draw draw a shadow of 'self' on 'screen' respecting the light-'source'.
"""
if not self: # empty
return
# point
elif len(self) == 1:
Ray(self[0], self[0] - source, color=color).draw(screen, offset)
# line
elif len(self) == 2:
# edgecase: would lead to DivisionByZeroError
if self[0] == source or self[1] == source:
for point in self:
Ray(point, point - source, color=color).draw(screen, offset)
return
# corners of screen area
rect = screen.get_rect()
corner = Vector(*rect[2:]) / 2
corners = [
corner * Vector( 1, 1),
corner * Vector(-1, 1),
corner * Vector(-1,-1),
corner * Vector( 1,-1),
corner * Vector( 1, 1),
corner * Vector( 1,-1),
]
# rays from source to both ends
ray1 = Ray(self[0], self[0] - source)
ray2 = Ray(self[1], self[1] - source)
# garantees anticlockwise order (important for calculations)
if ray1.dir.angle_to(ray2.dir) > 180:
ray1, ray2 = ray2, ray1
# creates minimal polygon
shadow = Polygon(color=color)
shadow.append(ray2.offscreen(screen, offset))
shadow.append(ray2.start)
shadow.append(ray1.start)
shadow.append(ray1.offscreen(screen, offset))
# adds corners of screen to polygon if needed
for i, _ in enumerate(corners[1:-1]):
if corners[i].is_between(ray1.dir, ray2.dir):
if corners[i-1].is_between(ray1.dir, ray2.dir):
shadow.append(offset + corners[i-1])
shadow.append(offset + corners[i])
if corners[i+1].is_between(ray1.dir, ray2.dir):
shadow.append(offset + corners[i+1])
break
# finally draws calculated shadow
shadow.draw(screen, offset)
# polygon
else: # draws shadow for every line in polygon
for i, _ in enumerate(self[:-1]):
Polygon(self[i], self[i+1]).draw_shadow(screen, offset, source)
Polygon(self[-1], self[0]).draw_shadow(screen, offset, source)
def dist_to(self, source):
"""
Return euclidean distance to the player ('source').
"""
def sdf_line(a, b, p):
"""
Return distance from point p to line a-b.
(source: https://youtu.be/PMltMdi1Wzg)
"""
if b == a:
h = 0
else:
h = min(1, max(0, (p-a).dot(b-a) / (b-a).dot(b-a)))
return ((p-a) - h * (b-a)).length()
if not self: # empty
return float('inf')
# minimum distance to a side
m = float('inf')
for i, _ in enumerate(self):
m = min(m, sdf_line(self[i-1], self[i], source))
return m
def cut(self, source, portal):
"""
Return 'self' but cut to fit in the view from 'source' though 'portal'.
This algorithm isn't perfect, but the best I got at the moment.
"""
def position(point):
"""
Return the area 'point' is in:
-1 -- in the triangle between source and portal line
0 -- to the right of visible area
1 -- in the visible portal area
2 -- to the left of visible area
"""
vec = point - source
if vec.is_between(ray1.dir, ray2.dir):
if (point - ray1.start).is_between(ray1.dir, border.dir):
return 1
else:
return -1
if vec.is_between(null, ray1.dir):
return 0
if vec.is_between(ray2.dir, null):
return 2
# rays that are borders of different areas
ray1 = Ray(portal.start, portal.start - source) # area 0 <--> 1
ray2 = Ray(portal.end, portal.end - source) # area 1 <--> 2
border = Ray(ray1.start, ray2.start - ray1.start) # area -1 <--> 1
null = -(ray1.dir + ray2.dir) # area 0 <--> 2
# garantees anticlockwise order (important for calculations)
if ray1.dir.angle_to(ray2.dir) > 180:
ray1, ray2 = ray2, ray1
rest = Polygon()
rest.__dict__ = self.__dict__
if not self: # empty
return rest
# edgecase for when a portal is in its own portal world in the same place
if len(self) == 2:
if self[0] in portal and self[1] in portal:
return rest
# algorithm for cutting polygon
nxt_pos = position(self[-1])
for i, _ in enumerate(self):
cur_pos = nxt_pos
nxt_pos = position(self[i])
if cur_pos == 1: # visible
rest.append(self[i-1])
# same position, nothing changes
if nxt_pos == cur_pos:
continue
# different position, intersections with visible area needed
inter = []
# through the left or right boundary of visible area -> intersection
if 1 in (cur_pos, nxt_pos):
if 0 in (cur_pos, nxt_pos):
inter += ray1.intersect(Ray(self[i-1], self[i] - self[i-1]))
elif 2 in (cur_pos, nxt_pos):
inter += ray2.intersect(Ray(self[i-1], self[i] - self[i-1]))
if not inter: # empty
inter += border.intersect(Ray(self[i-1], self[i] - self[i-1]))
# line goes outside the visible area around the portal -> edges of portal
elif -1 in (cur_pos, nxt_pos):
if 0 in (cur_pos, nxt_pos):
inter += [ray1.start]
else: # 2
inter += [ray2.start]
# line goes from the left to the right -> may intersect visible area
else: # 0 and 2
if cur_pos == 0:
inter += ray1.intersect(Ray(self[i-1], self[i] - self[i-1]))
inter += ray2.intersect(Ray(self[i-1], self[i] - self[i-1]))
else: # 2
inter += ray2.intersect(Ray(self[i-1], self[i] - self[i-1]))
inter += ray1.intersect(Ray(self[i-1], self[i] - self[i-1]))
# add intersections
for pt in inter:
if pt.length2() > 10000: # hotfix
print(f"CalculationError while cutting {self} at {ray1, ray2}:\n {pt} is very big")
else:
rest.append(pt)
return rest
[[#top|↑ Back to top]]
----
==== Floor ====
import colors
from polygon import *
class Floor(Polygon):
"""
Subclass for polygons as floor tiles wich don't have collisions.
"""
def __init__(self, *points, color=colors.DARK_RED):
"""Initilise 'self' with standard color 'DARK_RED'."""
Polygon.__init__(self, *points, color=color)
def draw_shadow(self, screen, offset, source, color=None):
"""Overide 'draw_shadow' to not draw a shadow."""
pass
def cut(self, source, portal):
"""
Return 'self' but cut to fit in the view from 'source' though 'portal'.
Makes use of 'Polygon.cut'.
"""
rest = Polygon.cut(self, source, portal)
if len(rest) > 2:
return Floor(*rest, color=self.color)
else:
return Polygon()
def dist_to(self, source):
"""Overide 'dist_to' to never cause collisions."""
return float('inf')
[[#top|↑ Back to top]]
----
==== Portal ====
import colors
from polygon import *
from matrix import *
class Portal(Polygon):
"""
Portal class as a 2-element 'Polygon' object.
In for both sides of the portal there is
an offset vector and a distortion matrix.
"""
# constructor: create self as Polygon object
def __init__(self, start, end, M=((1,0),(0,1)), M2=None, offset=None, offset2=None, color=colors.BRIGHT_BLUE):
"""
Initilises 'self' with standard color 'BRIGHT_BLUE'.
offset -- for side 1 (std: None == portal will remain in same place)
offset2 -- for side 2 (std: None == portal will remain in same place)
M -- distortion matrix for side 1 (std: unit matrix)
M2 -- distortion matrix for side 2 (std: None == inverse of M)
"""
Polygon.__init__(self, start, end, color=color)
self.M = Matrix(*M)
if M2 is None:
self.M2 = self.M.inverse()
else:
self.M2 = Matrix(*M2)
if offset is None:
self.offset = None
else:
self.offset = Vector(*offset)
if offset2 is None:
self.offset2 = None
else:
self.offset2 = Vector(*offset2)
def __getattr__(self, attr):
"""
Return 'self[0]' and 'self[1]' as attribute 'start' and 'end'.
"""
if attr == 'start':
return self[0]
if attr == 'end':
return self[1]
def go_through(self, dir, world):
"""
Return the portal world of 'world' for the side in direction 'dir'.
"""
portal_world = []
for object in world:
port = object.__class__(*object)
port.__dict__ = object.__dict__
# gone through side 1
if dir.is_between(self.end - self.start, self.start - self.end):
for i, _ in enumerate(object):
if self.offset is None:
# middle of portal in portal world
offset = self.M.prod((self.start + self.end) / 2) - (self.start + self.end) / 2
else:
offset = self.offset
# apply distortion and offset
port[i] = self.M.prod(object[i]) - offset
# if world gets mirrored the side-sensitive portals have to be reverted
if type(object) is Portal:
if self.M.i.angle_to(self.M.j) > 180:
port[0], port[1] = port[1], port[0]
# gone through side 2
else:
for i, _ in enumerate(object):
if self.offset2 is None:
# middle of portal in portal world
offset2 = self.M2.prod((self.start + self.end) / 2) - (self.start + self.end) / 2
else:
offset2 = self.offset2
# apply distortion and offset
port[i] = self.M2.prod(object[i]) - offset2
# if world gets mirrored the side-sensitive portals have to be reverted
if type(object) is Portal:
if self.M2.i.angle_to(self.M2.j) > 180:
port[0], port[1] = port[1], port[0]
# add distorted object to portal world
portal_world.append(port)
return portal_world
def portal_world(self, world, source):
portal_world = []
for object in world:
port = object.__class__(*object)
port.__dict__ = object.__dict__
# gone through side 1
if (self.start - source).is_between(self.end - self.start, self.start - self.end):
for i, _ in enumerate(object):
if self.offset is None:
# middle of portal in portal world
offset = self.M.prod((self.start + self.end) / 2) - (self.start + self.end) / 2
else:
offset = self.offset
# apply distortion and offset
port[i] = self.M.prod(object[i]) - offset
# if world gets mirrored the side-sensitive portals have to be reverted
if type(object) is Portal:
if self.M.i.angle_to(self.M.j) > 180:
port[0], port[1] = port[1], port[0]
# gone through side 2
else:
for i, _ in enumerate(object):
if self.offset2 is None:
# middle of portal in portal world
offset2 = self.M2.prod((self.start + self.end) / 2) - (self.start + self.end) / 2
else:
offset2 = self.offset2
# apply distortion and offset
port[i] = self.M2.prod(object[i]) - offset2
# if world gets mirrored the side-sensitive portals have to be reverted
if type(object) is Portal:
if self.M2.i.angle_to(self.M2.j) > 180:
port[0], port[1] = port[1], port[0]
# add distorted and truncated object to portal world
cut = port.cut(source, self)
if cut: # not empty
portal_world.append(cut)
return portal_world
def draw(self, screen, offset):
"""
Draw the endpoints of 'self' on 'screen'.
"""
for point in self:
Polygon(point).draw(screen, offset)
def draw_shadow(self, screen, offset, source):
"""
Draw draw a shadow of 'self' on 'screen' respecting the light-'source'.
"""
# draw the shadow in the same color as the background to wipe the canvas
Polygon.draw_shadow(self, screen, offset, source, color=colors.GRAY)
# draw shadows for the end points of portal
for point in self:
Polygon(point).draw_shadow(screen, offset, source)
def cut(self, source, portal):
"""
Return 'self' but cut to fit in the view from 'source' though 'portal'.
Makes use of 'Polygon.cut'.
"""
rest = Polygon.cut(self, source, portal)
if len(rest) == 2:
return Portal(*reversed(rest[:2]), M=self.M, color=self.color)
return Polygon()
[[#top|↑ Back to top]]