Download the release version here:
neg-world-engine.zip

Or download the newest version from the Git repository:
https://gitlab.tubit.tu-berlin.de/srather/NEG-World-Engine.git

Root: README, main

• Datatypes: Vector, Matrix

• Drawables: drawable, Ray, Polygon, Floor, Portal

• Utility: colors, generate, draw

drawable.py

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

↑ Back to top

ray.py

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])

↑ Back to top

polygon.py

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

↑ Back to top

floor.py

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')

↑ Back to top

portal.py

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()

↑ Back to top