Douglas Miller
patreon
MiP B2 Chapter 15: Spellcraft Analysis
🕑 Added 2024-07-16 17:02:18 +0000 UTC<< First | < Previous | Next >
Carlos listened intently as Trinlen spoke the incantation for Find Path, alert for whatever intriguing things he might learn.
spell begin;
use mana = from pool;
limit mana = 50% capacity;
Carlos nodded in appreciation at the unfamiliar variant in how the spell began. With that, I won't have to predict in advance how much mana a spell needs. Nice!
Trinlen had paused briefly with a knowing smile, but resumed incanting after only a moment.
parameter location = target;
parameter east = 2134.2;
parameter south = 788.6;
parameter down = 46.9;
effect displaceLocation;
variable destination = result;
Aha! Incantations do support variables and storing calculated values. I was starting to wonder, with how much of the effects catalogue I've gone through and still hadn't found anything for that.
parameter firstLocation = target;
parameter secondLocation = destination;
effect distance;
variable distance = result;
variable detourLimit = 1000;
label restart;
Label? Carlos frowned. Please tell me that's not for what I think it's for…
variable current = target;
effect makeList;
variable path = result;
parameter list = path;
parameter value = current;
effect append;
variable length = 1;
effect makeList;
variable reached = result;
parameter list = reached;
parameter value = current;
effect append;
Cumbersome list manipulation, but I expected that, really. Effects in general are all cumbersome to use in this travesty of a language.
loop begin;
parameter location = current;
parameter distance = 0.5;
parameter directions = cardinals;
parameter orderCriterion = proximity;
parameter proximalLocation = destination;
effect listNeighbors;
Carlos snorted in amusement. Special parameter options for ordering the list by proximity to somewhere are not an immediately obvious and natural design choice for that. I bet one of the system designers got frustrated with having to include code for sorting the list in their incantations, and abused their system access to make an invokable utility function for the sorting the only way they knew how to.
parameter loopList = result;
parameter loopVarName = neighbor;
loop begin;
Oh, iteration over a list. Great, that's major for all kinds of data processing logic.
parameter firstLocation = neighbor;
parameter secondLocation = target;
effect distance;
variable firstDistance = result;
parameter firstLocation = neighbor;
parameter secondLocation = destination;
effect distance;
variable secondDistance = result;
parameter firstValue = firstDistance;
parameter secondValue = secondDistance;
effect add;
parameter firstValue = result;
parameter secondValue = distance;
effect subtract;
Geeze, did they have to make basic math that cumbersome too?
parameter value = result;
parameter upperBound = detourLimit;
parameter failureGotoLabel = nextNeighbor;
effect compareLessThan;
Carlos slapped his forehead loudly. Oh god, that label thing is what I thought. They have conditional branching, and they implemented it with goddamn fucking goto! Ugh. He realized Trinlen had stopped talking. Carlos lowered his hand. "Sorry, continue."
parameter loopList = reached;
parameter loopVarName = reachedLocation;
loop begin;
parameter value = neighbor;
parameter avoidedValue = reachedLocation;
parameter failureGotoLabel = nextNeighbor;
effect compareNotEqual;
loop end;
Linear search of a list. Well, that'll be an obvious optimization, at least in concept.
parameter firstLocation = current;
parameter secondLocation = neighbor;
parameter width = 0.5;
effect lineSegment;
variable connection = result;
parameter region = connection;
effect scanDensity;
parameter value = result;
parameter upperBound = 120;
parameter failureGotoLabel = nextNeighbor;
effect compareLessThan;
So… If there's too much stuff in the way, then that's a barrier, I guess is what this is doing?
parameter region = connection;
effect scanCohesionStrength;
parameter value = result;
parameter upperBound = 80;
parameter failureGotoLabel = nextNeighbor;
effect compareLessThan;
Or if stuff is too strong, that's also a barrier. I think that's the logic here.
parameter location = neighbor;
parameter direction = down;
parameter weight = 300;
effect distanceOfSupportSurface;
parameter value = result;
parameter upperBound = 5;
parameter failureGotoLabel = nextNeighbor;
effect compareLessThan;
Carlos laughed and shook his head, but quickly waved for Trinlen to continue. Couldn't that system effect for finding a support surface be used for detecting barriers too? I'd bet it's a lot more reliable at it than fiddling with checking density and material cohesion. He sighed. Cargo cult programmers. Bah!
parameter list = path;
parameter value = neighbor;
effect append;
parameter list = reached;
parameter value = neighbor;
effect append;
setVariable current = neighbor;
increaseVariable length = 1;
parameter label = continue;
effect goto;
Carlos groaned. A straight-up unconditional goto? How much of a mess of spaghetti code is this going to be?
label nextNeighbor;
loop end;
parameter list = path;
effect removeLastElement;
parameter list = path;
effect getLastElement;
setVariable current = result;
decreaseVariable length = 1;
parameter value = length;
parameter targetValue = 0;
parameter failureGotoLabel = continue;
effect compareEqual;
multiplyVariable detourLimit = 2;
parameter label = restart;
effect goto;
label continue;
Carlos raised a hand for Trinlen to pause while he tried to sort out his understanding of the last several lines. Um. Okay, this thing is trying one path, attempting the most optimistic direct approach first, avoiding anywhere it's already explored, then backtracking every time it hits a dead end? And it tracks the path length manually, and if literally everything within the allowed size of a detour is all dead ends, then it starts over with allowing larger detours? He slowly nodded and lowered his hand.
loop while = (current notNear destination);
Wait, that sounded like actually semi-reasonable non-cumbersome expression syntax. Is this a special case, or have people just not figured out the generalization? Though, shouldn't there be a parameter for defining what counts as "near?"
loop begin;
parameter loopList = path;
parameter loopOrder = reverse;
parameter loopVarName = pathStep;
loop begin;
…
So, at this point in the code it's found a path, and it's iterating through that path to do… What, exactly? Optimize the path? It could certainly use that, since the initial search algorithm is far from guaranteed to find an optimal path. Carlos started ignoring minutiae of the spell's wording in favor of focusing on building a complete picture of its abstract conceptual design. Soon enough, he had his answer. Yep, it's finding corners that can be cut, loops that can be shrunk or short-circuited, aimless wandering detours that can be straightened, and so on.
Eventually, Trinlen's incantation finally came to its end and he set the spell loose. Carlos caught a brief glimpse in his mana sense of impressions of the spell busily scanning a series of half-foot sections, but its focus zoomed east into the distance immediately. In a tiny fraction of a second, it was farther away than he could sense, though he could still feel its connection to Trinlen. Mana was steadily flowing into the spell from the academy-trained mage's mana pool to continue powering its search.
Trinlen looked appraisingly at Carlos, briefly switched to Amber, then focused on Carlos again. "You clearly understood all of that, despite its use of words that were new to you. You have a truly incredible house secret, but it's not my place to pry about that. What do you think of the spell?"
Carlos's eyes twitched as he struggled to hold back from expressing his utter disgust. He resorted to telepathically griping to Amber just to vent some of the feeling. [Amber, you have no idea how much I want to sit down, right here and right now, and completely rewrite that… that atrocity of a pathfinding algorithm! I'm fairly sure it technically works, but its design is so horrible that its very existence offends me.] He slowly took a deep breath and focused on wrestling his expression back under control. When he noticed Amber struggling to hold back some laughter, he couldn't help but chuckle a bit too.
Carlos shook his head and tried to put his urge to fix that incantation out of his mind. Now is not the time for that. I can do it later, when I know more and have proper tools for the task. He looked back at Trinlen, who was patiently waiting with a raised eyebrow. "Yes, I did understand all of it. Some of the ways it does certain things will be very useful for us. For the spell overall…" He hesitated, uncertain how much he should actually say. "I understand how it works, and I have some ideas for improving it. We can discuss that later, when we're not in the middle of delving a dungeon."
Trinlen shrugged. "We're just waiting for the spell to finish at the moment. Do you have anything better to do until it's done? Come on, man, I'm dying to know what your reactions were about! Please?" He raised his hands together in front of him as if to beg.
Carlos sighed and shook his head sadly. "A proper explanation will take longer than any reasonable amount of time your spell might take." He paused. "How long will your spell take, anyway?"
"Depends on how much sidetracking it has to do. Could be up to about 20 minutes."
Carlos considered briefly, but then shook his head. "Tonight, after we've set up camp. Bring a written copy of the spell for me to reference. Until then, have patience."
After a few more minutes, Carlos sensed the spell's incessant scanning blip into and out of his sensing range. It was far to the east, and gone again almost as soon as he sensed it. Then it appeared again, and again, each time just slightly closer and in range slightly longer. It kept making a series of sweeps, from south to north, then north to south, alternating with each subsequent pass. It still zoomed along rapidly, but it was noticeably slower than when it originally went east, and it seemed to be flickering as it moved.
Carlos turned to look toward what he was sensing and focused on analyzing it. As I thought, it's taking longer and longer at each step to check whether a candidate next step goes to somewhere it's already explored or not. And depending on how far out of its way the opening to go down is, it might have to start over and rescan everything. He cocked his head. Wait, I think it does the restart by just going back to before the progress trackers are initialized. It repeats the initialization of them without clearing the old lists. Is that a memory leak? Actually, no, does the concept of memory leaks even mean anything for spells?
The rapid incremental scans gradually crossed over the area Carlos could sense and out the other side. A couple more minutes after that, the scans suddenly reappeared right next to Lorvan and flickered toward the southwest. Variations of that happened a few more times, and then Trinlen exclaimed in triumph. "Got it! Path to the core is that way." He pointed southwest.
Trinlen led them a few hundred feet southwest, then pointed at an innocuous carpet of leaves that looked no different from the ground around it. "Step on that, and you'll fall right through. It's the entrance to the lower floor."
Carlos examined it cautiously. "It's supported very weakly by a little dungeon magic, set to let anything heavy fall through while still holding up the rest of the leaves. If I didn't know better, I'd think it's just a hidden pit trap and avoid it."
Haftel laughed from the rear of the group. "You have no idea how many young adventurers have been fooled by exactly that mistake and wandered this forest until they gave up, never finding the dungeon's core. There are plenty of actual pit traps scattered around this dungeon that look identical to that from above."
Carlos nodded. "A clever ploy. This has only a short drop at first, though, right Trinlen? Your spell wouldn't explore a drop of more than 5 feet, I think."
Trinlen nodded, grinning widely. "Impressive understanding. Yes, there's a ledge just 3 feet down at first. It goes down a steep series of ledges for a bit, then levels out, and from there the rest of the path is pretty direct."
"Let's get going, then." Without further ado, Carlos poked a foot through the leaves, took a quick look, and hopped down.
There were a few more traps and monsters along the way through the dirt-and-root-walled caves that followed, but nothing truly threatening until near the end. With just 100 feet left to go, Carlos took one look around the corner at the 15-foot-long prowling tiger, with its massive muscles rippling visibly even through its thick black and orange striped fur, and shook his head. "I am not ready to fight that. Lorvan… Actually, let it sense how powerful you are and give it an opportunity to withdraw without a fight first. If it attacks you or refuses to retreat, then kill it."
Lorvan paused, then nodded. "As you command, my lord." He strode forward, and Carlos almost staggered as a tremendous weight seemed to suddenly descend on the entire area. The great tiger's head snapped up to stare at Lorvan, and it froze in that position. The royal guard locked gazes with the tiger and advanced slowly, spear in hand and his soul blazing with bared power. He gestured firmly to the side, paused, then waved his spear threateningly and settled in place to wait.
The tiger's ears were flat against its head, and it flinched at something. It growled, the sound filling the cave with a deep rumbling, but the growl somehow seemed more unhappy than aggressive to Carlos. It faded into a whine after a few seconds, and the tiger reluctantly lowered its head and looked away. It slowly backed up to the relatively narrow passage to the core room, then through it and out of sight, though Carlos could sense the mana in it settling down just behind the dungeon core itself.
The feeling of weight bearing down on everyone vanished, and Carlos advanced and beckoned everyone to follow. He continued until he could see the core, then paused to take in the sight.
This dungeon core was again unlike any other he'd seen. Its shape was regular and smooth, but not a prism. It was a vertical ovoid, almost shaped like an egg but with both ends narrow, about 7 inches tall and 4 inches wide. It glowed a vivid emerald green. Shifting shadows periodically fluttered across its surface, but the light illuminating its surroundings remained perfectly steady. It floated above a cradle of bright green leafy branches. The 15-foot tiger sat on the ground behind the core and glared, its fur tinted green by the core's light.
Carlos took a deep breath and looked at Amber by his side. "Amber, you said you wanted to try taking the lead on this one. You're up."
<< First | < Previous | Next >
I think the incantation I wrote should technically work, but I'm not 100% certain, since I can't actually test it. I won't be surprised if it has at least a small bug or two. I noticed while I was writing Carlos's mental commentary that I'd forgotten to actually add anything to the list of reached locations.
I aimed to make it function correctly, while being plausible as the product of someone reasonably smart but without the accumulated knowledge base of a major industry to build upon.
Sorry, but I am not going to write the path optimization part of it. Writing the crime against decency of algorithm design that I already put in this chapter was quite enough, thanks.
Comments
John
TYFTC
Pheonixarcher
Is it wrong that I want him to build a projectable interface for working on this stuff? Like he builds a test environment for spells. Basically builds an interface, interacts with code, and a testing space he can play with spells in. This sound like a blank unreal engine world or something
Pheonixarcher
I just want him to complain that he knew people who could make something that took a day to run he could optimize it to take less than a second. Just reminds me of those guys on youtube who optimize code to make it 1,000,000% faster.
Mark Nelson
The Memory Leak is likely handled outside of the spell itself. When a spell stops being processed or runs out of mana. The shaped mana containing the data of the spell likely dissolves. Also mana does not seem to care about density of itself.
Chase
Feel like a crackhead, keep lookin for the new post.
David Ellis
I was actually past that phase when Gentoo got big. I wrote modelines by hand for my dad's analog projection wide-screen TV for Red Hat 9.0 (not RHEL, just Red Hat) in the late 90s. By the point Gentoo was a meme I was 50/50 Ubuntu and OS X (home and work, respectively).
Maurice Brown
He hurts us because he loves us…
Maurice Brown
…you did a lot of Gentoo ahem optimization didn’t you..
Hilton Janfield
First step to an MMO where you have to cast magic by writing functions :)
Hilton Janfield
Search SWAG for some old Pascal pathfinding code optimized with ASM. It'll probably look a lot like what you wrote with a mix of low-level ASM inline functions for speed and high-level Pascal code for things like list management. Once upon a time we wrote things to optimize for speed. Today is all bloat. It's libraries all the way down... As far as UI response and general use, my 486/33 and P75 felt faster than my Core i7 does.
Ben Bass
TYFTC! I love how Carlos is critiquing the spell as it is being cast. It will be very interesting what his programming skills can bring to the table without a full IDE, and what his debugging structure will help him do with these completely unoptimized spells.
Neshura
I think it's hard to not make decent changes to this garbled mess
Neshura
same, I have no experience in writing compilers (or in this case interpreters) but I'm absolutely tempted to try, if anything only to see these horrid code fragments in 'action'
pfreya
Oh man, I’d absolutely be down to contribute to an open source implementation of this magic language and a VM to run it if that ever became a thing
Sid_Cypher
The program does remind me of Shenzhen I/O, though.
Josh
> I aimed to make it function correctly, while being plausible as the product of someone reasonably smart but without the accumulated knowledge base of a major industry to build upon. It also feels plausible as being what someone who is dealing with a language closer to assembly than a high-level language would write. When you have the benefit of a high-level language, it's much easier to consider writing something more complex. When you're writing in a very low-level language, and one that probably has no debugging tools either, you sometimes want to do the simplest thing that can possibly work, unless you absolutely *have* to optimize it.
Josh
> Carlos snorted in amusement. Special parameter options for ordering the list by proximity to somewhere are not an immediately obvious and natural design choice for that. I bet one of the system designers got frustrated with having to include code for sorting the list in their incantations, and abused their system access to make an invokable utility function for the sorting the only way they knew how to. Eh, that one seems perfectly reasonable. Depending on how the universe is organized and what data structures the magical system substrate uses, it may genuinely be more efficient to return the list in sorted order rather than sorting it afterwards.
David Ellis
I half expected that you wrote a shitty search algorithm, compiled to assembly with `-funroll-all-loops`and then translated that into a weird quasi-Javascript and finally replaced some things to make it magical (plus converting one loop into a statement because you got tired of the inanity)
ShadeByTheSea
Likely because with magic you have to actually supply the water(mana).
Petr Pavelka
There is nothing wrong with goto statements if you follow certain patterns. Some low level or older languages have only goto statements. Any higher language control structures are technically converted to jump instructions during compilation because cpu only understands jumps or conditional jumps. I am bit surprised that author of that algorithm did not inspire himself in nature. For example imagine a labyrinth and infinite source of water, you pour water into it until it reaches destination and every second you track which intersection/split already has water in it and where the water came from to it first. It eliminates problem of loops and finds the shortest path. It is easy to imagine and therefore easy to build a functional algorithm using that idea. The main downside is that it would be memory intensive.
viperfan7
I bet notepad yelled at you then crashed when you tried to save it
Maurice Brown
[laughing in O-notation]
Douglas Miller
While I was writing it, I struggled to not cringe. 🤣
viperfan7
Why would you hurt me like that. You are a truly evil person
Marconi H Gonçalves
I don't think I'll have any excuses to learn a programming language, even a layman like me of current languages, this compilation is worse than the Basic and Fortran that I learned...
Connor Mcharg
Thanks, I hate it, and now I’m going to get a good night’s sleep, re-read it, and try to run it manually for testing reasons.
Ben Riker
My man. Everything compiles on paper. That said if you ever want to mock up your own language it would be an awesome project.
Logos
In another world, in another time. Edsger Dijkstra suddenly stops pacing back and forth in his office. "Goto statements!" he seethes quietly, before continuing his pacing.
Olli Erinko
As a developer myself, this chapter was especially painful to read. I hope the camp optimizations are decent :D
Test Patron Plz Ignore
First!
