DEV Community: Joseph Daws Jr.

Setting the scope for alphabet superset 2023

Joseph Daws Jr. — Thu, 24 Aug 2023 02:42:18 +0000

The YouTube algorithm has revealed to me some of my favorite media. This week it gave yet another unearned surprise (well I guess I paid for it by watching YouTube ads XD). The YouTuber struthless released a call to action for creative people to build 26 parts of a cohesive body of work in 26 weeks (one week for each letter of alphabet). Although I'm feeling fulfilled in my day job, I was feeling in a bit of a rut on my side projects. I haven't made progress on my simulation of eldritch beings in a few months. I think ALPHABET SUPERSET is a good chance to make some progress on my creative endeavors. So following the guide provided, here is my attempt to properly scope and define a theme for my 26 creations.

Week 1 -- constraints

The goal of weeks 1 and 2 is prepare a creative framework to make the 26 weeks streamlined. In week one struthless asks creatives to contemplate certain constraints to guide a framework where your creativity will bloom. I really appreciate this guidance. So far in my project I've just let my creative heart dictate scope expansion after scope expansion. Even though I've never used them seriously in creative work, I do believe well chosen constraints accelerate creativity! The constraints are

medium constraints
style constraints
output constraints
theme constraints

Medium Constraints

Core Medium

I intend to make my simulation of eldritch beings as my core medium of creativity. This will include building a UI for viewing the simulation and interacting with it. I need to learn about how to design a properly compelling "game loop" to keep the viewer/player engaged with the simulation. Right now it's a bit aimless. My original goal was to create a simulation of a system which invites the viewer to question how agents interacting in a system both influence and become influenced by the system. And in particular, what kind of systems tend to encourage agents to behave selfishly, and which kinds of systems encourage and reward agents to take actions which benefit the others? I don't have a solid plan for conveying this, so I hope to figure it out in part by partaking in this exercise.

Communication Medium

I'd like to use blog posts here on dev! I'll also make direct updates to my UI and simulation itself.

words and drawings
Simple UI work using scenic
Simulation built using elixir

Style Constraints

Five aesthetic rules

UI assets will be created with pen and paper this is consistent with the initial design of the UI being a book
Unique and specific beings will be prioritized over fully procedurally generated beings
Sound is not to be integrated into the UI
Animations are not to be integrated into the UI
Keep is simple, if I can't figure out how to implement it in a week, then it's not going to be built during alphabetsuperset

Output Constraints

What thing will you make every week

1 asset, 1 design choice, 1 story element, or 1 code improvement to the simulation.

How will you post this every week

I'll create a tweet or a blog post (or both about the creation). This will require the additional work of writing down what was created and why it was created.

How long will this take

I guess about 3 -- 6 hours per week.

Theme Constraints

My theme is systems and relations of eldritch beings

Systems and relations are core components which influence individual behavior. They are themselves also influenced by a collection of individual actions. Understanding the relationships between systems and individuals acting in those systems is important to me because discovering and promoting systems and relations that support all individuals involved is a path for world growth and peace that I'd like to advocate for. However, there are major barriers to communicating about such things.

I'm not an expert in systems and relations and have limited capacity to communicate about it using prose or mathematics. I need to improve (and I think I can do this through this creative endeavour).
Communicating with others through purely informational or purely mathematical frameworks will have a limited reach. Stories and interactive media have a better chance of conveying what can be done to improve our systems and relations since they ground abstract ideas in familiar or semi-familiar narrative structures.
I am fascinated by "weird science fiction" and the Cthulhu mythos so it will be fun to united systems and relations with a specific genre of science fiction.

Conclusion

I'm not sure I've appropriately scoped the project, but that's part of the learning process. I'm also looking forward to seeing what other participants in alphabetsuperset create, especially those creating interactive media.

Toward a network model for Metroidvania Speed Run Routing -- Part 1

Joseph Daws Jr. — Fri, 29 Oct 2021 03:21:34 +0000

I've seen many posts and comments in various corners of the web asking

"Isn't speed run routing a kind of travelling salesman problem?"

"Isn't speed run routing a shortest path problem?"

Or any variant of this question. I also asked this question after taking a network flows course which used the classic network flows text by Ahuja, Magnanti, and Orlin. In that course, shortest path algorithms and max flow algorithms were discussed. I think the text explains the concepts well (after all I felt like I had some understanding after reading some of the chapters), but what especially stuck out to me were the applications. Chapter 19 is entirely dedicated to ways in which the previously described problems and algorithms can be used to frame and solve real-world problems as network problems. Some of them, taken at face value, sound like they would be able to help in routing a speed run.

Shortest path problems seem helpful if you know you need to get from one point to another provided you have an appropriate graph model to describe the geography of the game.
Knapsack problems see useful for finding the most optimal collection of times in order to pass a portion of the game (I have in mind the number of missile expansions collected before facing a certain Super Metroid boss).

I still don't know how these pieces might fit together to actually find an optimal route, but that's what I aim to write about here. The general question seems to be,

"how might speed running routing be formulated as a network problem or combination of network problems?"

To answer this, I'll try to provide a problem formulation and an algorithm to solve the problem of finding the optimal route for a Super Metroid speed run (I'll defer talking about which category of speed run I want to consider until more details of the network model become apparent to me). Almost certainly, this will take me a good bit of time to think about, but I want to keep a log of my thoughts using these posts. Moreover, if you know that this kind of thing has already been solved, I'd love see what you've developed or discovered.

Goals

I enjoy consuming speed running content. I especially like to hear the details of how certain strategies came to be. By trying to formulate an automated process to route runs, I think it may lead to a good idea for a tool or app to help routers.

Why focus on Metroidvania?

Besides the fact that I find them very interesting and fun to play, I think they have certain properties which will make formulating the problem easier.

To define a network model useful for solving a real-world problem, one needs to define what the nodes and edges of the network represent.

Many Metroidvanias feature discrete rooms with a finite number of "doors" between them. This seems like a good place to start as it reduces the cardinality of paths one needs to consider (one might have a hard time quantifying how many paths between point A and point B there are in an open-world game like Skyrim). This finiteness also limits the number of ways in which nodes and edges can be associated with discrete game locations or objects.

Is it possible to prove the current WR route is optimal?

Many network problems, such as the shortest path problem, can be formulated as linear programs. This is a really nice class of problems because it is known when they have unique optimal solutions and when they do not. My gut feeling is there is no way that there is a formulation of speed run routing for which it is easy to know when an optimal solution exists and when it does not (regardless of whether there is an algorithm to find it if it exists). But it's still too early to tell. Wouldn't it be a happy surprise to find that the current world record route is also the one found by the algorithm?

Caveats

The algorithm I hope to find probably won't help a runner find new exploits or skips. Out of bounds paths can be considered in this algorithm if they are known already, but the algorithm won't search for new ways to get around the world.

A awesome category of speed run are randomizers. I don't feel confident the model will be directly helpful for routing a randomize Metroidvania.

An overly simplistic start

For the purpose of exploring different ways of formulating the problem, consider the overly simplistic Metroidvania, Super Simpl Land.

The game consists of 7 rooms labelled A to G.
The player can travel between rooms connected with an arrow.
The objective is to beat the final boss!
You must collect the key in room A to pass the barrier between rooms F and G.
There are items in room C and D.
While you don't need items to defeat the boss, it's easier and quicker to do the fight using items.

This setup represents my idea of a minimum viable Metroidvania (though I don't think this game would be much fun to play). It includes, collectables, a barrier which requires a particular collectable (the key) to pass, and multiple paths between certain rooms.

Super Simpl land is also interesting (slightly more interesting than trivial) from the routing point of view because different strategies can be compared. For instance, if it is much faster to beat the boss with both items obtained then it is worth the extra time to go get them. An algorithm to route this game would take this into account.

A network model for `Super Simpl Land`

My current goal is to form a network model which is helpful for routing this silly game. To that end, the first thing that occurs to me is to let the nodes represent partial paths in the game, e.g.

B --> A --> B --> E

is a partial path the player may take on their way to the boss.
The edges represent different to represent different ways to extend a current path. For example, the partial path above could become

B --> A --> B --> E --> D

B --> A --> B --> E --> F

The 3 nodes and two edges would look like

So the task is set. Is this even a useful model at all? I'm not sure yet, but this is what I'll work on until the next post.