Skip to content

Latest commit

 

History

History
542 lines (510 loc) · 25.5 KB

ROADMAP.org

File metadata and controls

542 lines (510 loc) · 25.5 KB

Roadmap

This is pool of tasks that should be implemented, roughly sorted by priority.

Specific tasks

implement target indicator

rebrand the engine

SVG Logo in ~/tmp.

add badges to description

See e.g. https://gitlab.com/michenriksen/jdam.

fix isometric coordinates math

submit to Quicklisp

Check if there are any warnings (adding :verbose t to ql:quickload).

add ability to specify entities in Tiled maps

replace CastleDB files with plain S-exprs

Something in the spirit of

(deftable impact-sounds
  (weapon-class armor-class sound
   :index (weapon-class armor-class))
  (:mandibles :flesh (:mandibles-flesh-1 :mandibles-flesh-2))
  (:fists :chitin (:fists-chitin-1 :fists-chitin-2))
  (:sword :chitin (:sword-chitin-1 :sword-chitin-2))
  ;; ...
)

Also perhaps rename LISP resource files to have “.sexp” extension.

fix twitchy attack bug

When you’re running away from mobs, they’re kinda twitch (lol) with their attack. Do not break attacking animation until it is finished (just as in D2).

fix minor target lock bug

Target lock sticks when going to main menu.

fix unhandled memory fault on condition in system-draw

add winning screen

Add some “thanks for playing” screen when the boss dies. Thanks to mrduckquacks from Twitch for the reminder :)

add character turn speed limit

This was not on original Diablo (but this feature was in Warcraft 3 engine anyway): the character’s turn speed is limited to some finite value.

consider implementing character sizes

Right now characters are just point particles. I should have the ability to set the sizes of them (radius, or width+height) somewhere (aseprite layer user data?) and take into account everywhere (pathfinding, collisions, target picking etc).

Maybe even use cylinder as a model, so have radius + height.

Perhaps this would solve sticking in fence corners problem.

Also seems like there’s bug related to attack-distance in combat system: when we want to close on the enemy, but the path from A* is empty and we set target to -1, sometimes this happens when you move towards the mob and it seems stuck.

Also there’s a bug with the character collision map: characters now stuck in each other (?)

see also https://gridsagegames.com/blog/2020/04/developing-multitile-creatures-roguelikes

create GUIX channel

is that how the thing’s called?..

implement A*

  OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
  current = remove lowest rank item from OPEN
  add current to CLOSED
  for neighbors of current:
    cost = g(current) + movementcost(current, neighbor)
    if neighbor in OPEN and cost less than g(neighbor):
      remove neighbor from OPEN, because new path is better
    if neighbor in CLOSED and cost less than g(neighbor):
      remove neighbor from CLOSED
    if neighbor not in OPEN and neighbor not in CLOSED:
      set g(neighbor) to cost
      add neighbor to OPEN
      set priority queue rank to g(neighbor) + h(neighbor)
      set neighbor's parent to current
reconstruct reverse path from goal to start by following parent pointers

g(n) represents the exact cost of the path from the starting point to any vertex n, and h(n) represents the heuristic estimated cost from vertex n to the goal.

On cost functions

On a square grid that allows 8 directions of movement, use Diagonal distance (L∞)

function heuristic(node) =
  dx = abs(node.x - goal.x)
  dy = abs(node.y - goal.y)
  return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)

where D is cost of rectilinear movement, and D2 is cost of diagonal movement. Seems like in our case D=D2=1 and the metric becomes Chebyshev distance: max(dx, dy).

A different way to break ties is to prefer paths that are along the straight line from the starting point to the goal:

dx1 = current.x - goal.x
dy1 = current.y - goal.y
dx2 = start.x - goal.x
dy2 = start.y - goal.y
cross = abs(dx1*dy2 - dx2*dy1)
heuristic += cross*0.001

And yet another way to break ties on grids is to minimize turns. The change in x,y from the parent to the current node tells you what direction you were moving in. For all edges being considered from current to neighbor, if the change in x,y is different than the one from parent to current, then add a small penalty to the movement cost.

Instead of checking both movement costs and for obstacles in your pathfinding algorithm, you can use movement costs. Just assign a very high movement cost to any obstacle. When expanding nodes (in the A* algorithm), check if the cost is too high; if it is, then throw the node out.

On non-reachability

If your game has situations in which the start and goal are not connected at all by the graph, A* will take a long time to run, since it has to explore every node connected from the start before it realizes there’s no path. Calculate the Connected Components first and only use A* if the start and goal are in the same region.

In some game maps, there’s no path between the source and destination. If you ask A* to find a path, it will end up exploring a large subset of the graph before it determines that there’s no path. If the map can be analyzed beforehand, mark each of the connected subgraphs with a different marker. Then, before looking for a path, check if the source and destination are both in the same subgraph. If not, then you know there’s no path between them.

Consider ALT A*

Consider Fringe search

It is possible to exit early from the A* main loop and get a partial path. Normally, the loop exits when it finds the goal node. However, at any point before that, it can return a path to the currently best node in OPEN. That node is our best chance of getting to the goal, so it’s a reasonable place to go.

On skipping trivial line path sectors

Sometimes grids are used for pathfinding because the map is made on a grid, not because you actually want movement on a grid. A* would run faster and produce better paths if given a graph of key points (such as corners) instead of the grid. However if you don’t want to precompute the graph of corners, you can use Theta*, a variant of A* that runs on square grids, to find paths that don’t strictly follow the grid. When building parent pointers, Theta* will point directly to an ancestor if there’s a line of sight to that node, and skips the nodes in between.

Jump Point Search, a variant of A* that can skip ahead on square grids. When considering children of the current node for possible inclusion in the OPEN set, Jump Point Search skips ahead to faraway nodes that are visible from the current node. Each step is more expensive but there are fewer of them, reducing the number of nodes in the OPEN set. See this blog post for details, this blog post for a nice visual explanation, and this discussion on reddit of pros and cons.

A waypoint is a point along a path. Instead of storing every step along the way, after pathfinding a post-processing step can collapse multiple steps into a single waypoint, usually at places where the path changes direction or at major locations like cities. The movement algorithm will then follow a path between waypoints.

improve A* performance

Overall performance is not great, but A* performance is notably bad - I was forced to make holes in the in-game fence just to make it not hang. Need to improve it, using some algorithmic tricks (see http://theory.stanford.edu/~amitp/GameProgramming) and/or better data types.

The nice basic performance would be finding way in “snake maze” 13x38 in less than 15ms.

Also while I’m on it, perhaps it is worth to penalize turns so the character movement looks more natural.

Useful links:

add possibility to reload prefabs from disk

Perhaps use continuable from livesupport?

use MacPorts for OSX builds

https://stackoverflow.com/a/75104694/1336774

consider prefab lazy loading

This way initial loading would not be that long.

add app icon

  1. Set app file icon in a cross-platform way. For Windows - Reshacker or rcedit?..
  2. Set running app icon with al:set-display-icon?

add nice custom cursor

https://liballeg.org/a5docs/trunk/mouse.html#mouse-cursors

These will do: https://opengameart.org/content/pointers-part-5

add support for external tiled tileset

https://tinyurl.com/tmx-format?highlight=tsx#tileset

optimize loading time

By utilizing fast-io and/or bitio, just like the guys from Atlanta Common Lisp study group do. Also consider using trivial-mmap.

implement soundscape

  • static (e.g. water dripping)
  • dynamic (e.g. wind)

Reuse existing stuff (e.g. placing objects on map). Add background sounds (looping). See https://liballeg.org/a5docs/trunk/audio.html#al_set_sample_instance_playmode

lower requirements for max texture size

Tweak the way sprites are stored to comply with ancient video cards (e.g. store vertically or split in several textures).

optimize sprite batch

Here’s the idea: store the single machine word in priority-queue, splitting it into priority and index in some growable array, perhaps using SoA.

automatically build SBCL usable in older Windows OSes

fix messagebox on OSX

Message box on OSX is missing heading text (which is “We got a big problem here”, a really nice reference). Make pull request for liballegro fixing this with this.

add literate documentation

add “basics of Lisp” doc section for newcomers

d2clone-kit engine is written in Common Lisp, which is a language from the lineage of unique LISP family dating as old as 1957. There are a lot of features that were stolen into other languages over the course of time (e.g. conditional operator, garbage collection etc), but the most unique feature is homoiconicity, which basically means that there is no distinct line between the code and the data in LISP language, which in turn allows to easily script d2clone-kit based game and yet perform efficiently by compiling to native code. This article demonstrates the basics of Common Lisp needed to confidently create and modify d2clone-kit based games.

Also add “made with lisp” logo somewhere.

Refactoring

factor out ECS library

To a separate permissively licensed library to use it in other projects. Also deal with growable vector & sparse array.

move demo to a separate repositiy too

Copy build scripts from dld. Also add AppImage metadata.

split library in ASDF modules

See https://lisp-lang.org/learn/writing-libraries; see also https://github.com/koto-bank/lbge/blob/master/src/lbge.asd as an example.

use let-plus+alexandria instead of serapeum!

Or use metabang-bind, it is qbase64 dependency anyway.

think on using package local-nickname

See https://github.com/phoe/trivial-package-local-nicknames and https://gist.github.com/phoe/2b63f33a2a4727a437403eceb7a6b4a3.

make potion drinking into an action

Also add sound of leather handling (like getting the potion from belt).

change actions to components

  • Each action = separate component?..
  • Also perhaps typecase on the action type?..

rewrite *-traverse functions as macroses

Thus omitting extra CALL.

use dynamic-extent where applicable

For known-size stack-allocated objects (fixed size arrays and known structs).

implement condition types

And replace (error "error text") with (error 'error-type "text").

use wrapper for define-*

Use https://github.com/guicho271828/lisp-namespace (basically thin wrapper around hash-table) and/or https://github.com/Shinmera/definitions. Also have a look at https://common-lisp.net/project/definer and https://github.com/phoe/in-nomine.

consider replacing ppcre library

With https://github.com/no-defun-allowed/one-more-re-nightmare.

consider replacing xmls library

E.g. with https://shinmera.github.io/plump or https://cxml.common-lisp.dev/sax.html. Do a benchmark.

try damn-fast-priority-queue library

https://github.com/phoe/damn-fast-priority-queue

tweak DEFUNL, replacing CL:DEFUN with custom declaration

Add some kind of custom declaim, see http://lispworks.com/documentation/lw51/CLHS/Body/d_declar.htm#declaration.

consider using trivial-types

For some missing type specifications (e.g. plist)

Stuff to research

consider using Conventional Commits

https://conventionalcommits.org/en/v1.0.0

consider using Break Versioning

https://github.com/ptaoussanis/encore/blob/master/BREAK-VERSIONING.md

consider using nice reader library

https://quickdocs.org/reader

unit tests

See https://lisp-lang.org/learn/continuous-integration#gitlab-ci-and-docker. See also https://lispcookbook.github.io/cl-cookbook/testing.html. See also https://sabracrolleton.github.io/testing-framework.

Some testing libs:

Also see https://github.com/40ants/cl-hamcrest. Also test with different size of tile (see Kenney assets).

do changes according to Google CL style guide

https://google.github.io/styleguide/lispguide.xml

See also: a CL style tutorial from 1993, https://cs.umd.edu/~nau/cmsc421/norvig-lisp-style.pdf. See also https://github.com/foxsae/The-One-True-Lisp-Style-Guide.

think about resource system

have a look at one at Shinmera’s trial also see Shirakumo/trial#58

read about isometric map drawing

https://habr.com/ru/articles/767892/

add dungeon generation

add network game

Probably use player system’s component to store some actual player-specfic data. At least, MOUSE-PRESSED-P and LAST-TARGET from system most probably should go into player component.

Implementations:

dialogue DSL

paper: Representing Game Dialogue as Expressions in First-Order Logic

See also microtalespin story generator. Also have a look towards Prolog-style stuff, e.g. https://common-lisp.net/project/cl-unification. Also have a look at https://github.com/lang-party/Summer2022.

add illumination

Noise + alpha blending? Lightrays from the sky?..

add AI DSL

Your units may have more than one goal. For example, you may have a general goal like “spying” but also a more immediate goal like “go to the enemy headquarters”. In addition, there may be temporary goals like “avoid that patrol guard”. Here are some ideas for goals:

  • Stop: Stay in the current location
  • Stay: Stay in one area
  • Flee: Move to a safe area
  • Retreat: Move to a safe area, while fighting off enemy units
  • Explore: Find and learn about areas for which little information is known
  • Wander: Move around aimlessly
  • Search: Look for a particular object
  • Spy: Go near an object or unit to learn more about it, without being seen
  • Patrol: Repeatedly walk through an area to make sure no enemy units go through it
  • Defend: Stay near some object or unit to keep enemy units away
  • Guard: Stay near the entrance to some area to keep enemy units out
  • Attack: Move to some object or unit to capture or destroy it
  • Surround: With other units, try to surround an enemy unit or object
  • Shun: Move away from some object or unit
  • Avoid: Stay away from any other units
  • Follow: Stay near some unit as it moves around
  • Group: Seek and form groups of units
  • Work: Perform some task like mining, farming, or collecting

For each unit you can have a flag indicating which behavior it is to perform. To have multiple levels, keep a behavior stack. The top of the stack will be the most immediate goal and the bottom of the stack will be the overall goal. When you need to do something new but later want to go back to what you were doing, push a new behavior on the stack. If you instead need to do something new but don’t want to go back to the old behavior, clear the stack. Once you are done with some goal, pop it from the stack and start performing the next behavior on the stack.

read about GOAP

  • Artificial Intelligence: A New Synthesis
  • AI Game Programming Wisdom 2 (Game Development Series)

battle simulate macro or something

For testing and simulating map regions afar from current player position. Also maybe playtest macro starting main with specific set of systems, entities, random seed and other parameters.

main loop catching up

Have a look at Shinmera’s game loop re. delta-time and catching up restart: https://github.com/Shirakumo/trial/blob/94a0a9/render-loop.lisp#L53-L54.

Also from mfiano:

I handle this case specifically with a custom debugger hook that tracks how much time is spent in the debugger in order to subtract it from the running time of the game clock, so that the current and previous frame times don’t throw physics out of whack.

data-driven build

have build.sh script with parameter which is the name of the game (or rather the set of initial maps/entities to load). It should sink through asdf entrypoint into binary, which will just load the necessary assets. Plus maybe have debug option.

Source of inspiration: https://en.wikipedia.org/wiki/Inform.

also consider embedding resources into binary

Perhaps in-memory ALLEGRO_FILE or something.

Source of inspiration: build system in this project.

consider resource ZIP files signing (GPG?)

try out Clasp

consider using 40ants-critic in CI

https://github.com/40ants/40ants-critic

add CLisp CI job

Clisp has a few very compelling features: it’s written in very portable C and can produce small executables, the compiler is fast and the bytecode execution fast enough, and the compiler is strict and can detect portability issues better than the rest.

CI jobs for architectures other than x86

E.g. ARM64/Raspberry Pi. Travis CI? CircleCI seems to support ARM as well.

make releases from CI builds for demo

https://tinyurl.com/gitlab-release-cli

consider using tree-shaker before building

https://gist.github.com/burtonsamograd/f08f561264ff94391300

limit FPS

Perhaps it would improve performance a bit. Thanks to my friend Iliya for the tip.

See this forum post. Also maybe modify game loop to have fixed timestep or something, see https://gameprogrammingpatterns.com/game-loop.html and this answer.

consider using RNG from Dwarf Fortress

https://github.com/svaarala/duktape/blob/master/misc/splitmix64.c

consider using trivial-with-current-source-form library

For better macros. https://github.com/scymtym/trivial-with-current-source-form

consider using recompile library

https://github.com/40ants/recompile

consider using polymorphic-functions library

E.g. for systems? https://github.com/digikar99/polymorphic-functions.

consider using easing library

https://github.com/vydd/easing. Also see https://easings.net/en

consider using trivial-extensible-sequences library

For custom datatypes (priority queue, sparse array). https://shinmera.github.io/trivial-extensible-sequences

learn some architectural lessons from ViralityEngine

https://github.com/bufferswap/ViralityEngine

try out SBCL block compilation

optimize GC

By offloading big GC cycles to load screens and transitions. See Shinmera’s paper.

optimize memory accesses

Tools:

controller support

add color postprocessing

Have a look at https://vas3k.ru/blog/computational_photography.

try rendering profilers

Test Renderdoc with ALLEGRO_OPENGL_CORE_PROFILE. apitrace seems to work with liballegro. Also have a look at https://github.com/40ants/cl-flamegraph.

think about launching in the browser

Clasp -> LLVM bitcode -> Emscripten? Or ECL -> C -> Emscripten (see also https://common-lisp.net/project/ecl/posts/ECL-Quarterly-Volume-IV.html)? Or JSCL?.. See also https://allegro.cc/forums/thread/617023.