3 ms·
As a nightmare in the opposite direction, I've been writing a new pathfinding system for Second Life, from the user side. Where you get a maximum of 64KB per pr
by Animats 7y ago
As a nightmare in the opposite direction, I've been writing a new pathfinding system for Second Life, from the user side. Where you get a maximum of 64KB per program. KB. Not MB. And that's for code, stack, and data, using the Mono engine.
You can have many programs, and they can pass messages around, so you can do jobs that won't fit in one program. It's like coding for a cluster of Arduinos.
I've had to pack data into integers with shift operations. Come up with an efficient maze solving algorithm that only needs 2 bits per cell. Divide tasks into multi-step pipelines. Monitor memory usage and divide the data into smaller chunks that will fit. Plus it's soft real time and has to run properly under overload conditions when it can't get enough CPU time.
It's kind of neat to see autonomous characters running around the virtual world at running speed. This was believed to be impossible, but I got it working out of sheer stubbornness. It was far too much work.
(Second Life has a built-in pathfinding system. It's too buggy to use, and they refuse to fix it. This is a workaround.)
(Why such tiny programs? Because they are not only persistent, for years if necessary, but are copied from one machine to another, state and all, as objects move around.)
- Zelizz 7y agoThat's unreasonably cool. Do you think it consumes more resources than if they just gave you more than 64K to work with, or do you think you were pushed to optimize further because of the limitations?
- Animats 7y agoIt uses about 750KB total, spread over a dozen or so tiny programs. Probably 2x the memory and more CPU time because it's broken into so many pieces, both in time and code. And at least 2x-3x the development time. It pushed me to work on minimum-memory maze solving. It costs a lot to test a cell (this involves ray-casting in the simulated world) so something like A*, which examines most of the cells, is out. An algorithm in Wikipedia turned out not to work; some anon had snuck in a reference to an obscure paper of their own. Had to fix that. What I'm doing is "head for the goal, when you hit something, follow the wall, if it will get closer, head for the goal again". Wall following is both ways simultaneously, so you don't take too long on the long path when a short path is available. After getting a path, the path is tightened up to take out the jaggies. This is not optimal but is usually reasonably good. The rest of it is more or less routine, and a pain to break into sections. The programs have to communicate with JSON, over a weak IPC system with bad scheduling. I always liked the 3D "metaverse" concept. Second Life, which has about 30,000 to 50,000 users on line at any one time, comparable to GTA Online, is the biggest virtual world around. Everybody bigger is sharded, but all SL users are in one world. The technology needs a refresh, but every competitor who's tried to build a big virtual world has been unable to get many users. So, you're stuck with outdated tech if you want to get something used in a virtual world. I think they're still in 32 bit mode on the servers, even.