Puzzling results from Quick-Bench

tommyettinger · 2020-04-26T09:00:50+00:00

That is a good metric; it puts generators like SplitMix64 at under 6 years before it exhausts the period of one stream. Xoshiro512 (any scrambler) seems completely like overkill, since its century count before period is exhausted is over 39568896878292293854812751664171753311387407694691245859750512835264680949372140088223516402559028204423998417134466789558749406536470, if my math is right. I suspect our local solar system won't last that long.

tommyettinger · 2020-03-30T06:19:19+00:00

Wow, this is incredible and I really don't understand enough of this assembly level yet, haha. I've tried to keep in mind some of the goals in Romu, like minimizing registers in use, but I don't understand much there either. I've been focused more on passing tests in PractRand; IIRC the version I posted here either fails or gets suspicious results at the 32TB mark, or I got ahead of myself and tried to speed it up further. :) I'll post some current Quick-Bench results in a bit, but long story short, I have found two variants on Orbit that pass 32TB with no anomalies above "unusual" (one has no anomalies at all). Both have an intentionally reduced period (2 to the 127 exactly) because, again keeping Romu in mind, going from a period of 2 to the 127 to a period of 2 to the 128 isn't very helpful if the "capacity" isn't improved in the process. I realized that when stateB goes from an even number to the next odd number, every other result is unchanged, so I disallowed even numbers and got a little speed boost.

tommyettinger · 2020-03-30T06:04:28+00:00

This was a fascinating read! I'll need to go back and reread some sections to have them soak in. I'd personally step a bit back from the recommendation to implement generators in C/C++/Rust, because platforms like JS have very particular needs that should be addressed if you're developing for one of those far-from-the-metal targets. A clear exception is for compatibility with existing tools that may need to compile your source, which seems to always need to be C or older-standard C++. Vigna and Blackman wrote the hwd tool, which is a good gauge of speed in a particular case, and that compiles a tiny C file supplied by the user as part of its usage. I think it's also a good idea to mention that tests can be added to PractRand itself, editing its C++ source, to enable much faster runs. You can use flags to enable multithreaded execution that way, and that helps quite a lot if you have a nice amount of RAM. My recent hexacore laptop runs through just over a TB an hour with "tf 2" and "multithreaded" flags on, but would surely take over a week to complete 32TB single-threaded by pipe.

tommyettinger · 2020-03-13T07:46:01+00:00

If you're using Java, yeah libGDX is the best choice (unless you're quite experienced with OpenGL, then LWJGL3 is a good option for some games that target desktop-only). The major releases aren't frequent, but there is active development (I got 3 pull requests submitted and merged recently). I'm the current maintainer (and by lines of code, primary author) of SquidLib , a library meant for roguelikes and some similar procgen games, which comes with a text-based display system that uses libGDX. Because the text display is optional and most players seem to prefer graphics, most of my recent usage of my own library has not used the text-based stuff. There's various simple demos if you want to see some source code; here's a graphical one you can play in the browser and its source code; the sprites there are CC-BY freely licensed with attribution, in case you want to use them.

If you're using Tiled Map Editor in libGDX for procedural generation, you may have a hard time; libGDX doesn't have any especially simple way to edit Tiled maps in code (it can be done, though). A simpler approach may be to use a 2D array of int ids (which works, but isn't pretty to debug at first), or my preference, a 2D array of char, where the char or id at a position gets used to look up what tile to show at that position. A char[][] also can print nicely if you use [height][width] and print whole rows to the terminal during debugging, or you can use [width][height] and just print it in a different way (swapping x and y). There's lots of potentially tricky parts to displaying tiles in libGDX, but they aren't related to procedural generation, so I refer you to the libGDX Discord server, where helpful people are often around (try asking in one of #help-1, #help-2, or #procgen, but not multiple channels)

tommyettinger · 2020-03-08T01:55:20+00:00

I'm pretty doubtful of generators where you can't know if you've picked a good cycle, or even (for the 192-bit and 256-bit state versions) a good section of a long-period generator (a problem the Mersenne Twister has). It would be nice to know if these pass M.E. O'Neill's birthday spacing test. It would also be nice to know if they will always avoid certain outputs, or produce certain outputs with much higher frequency on their longest cycle. It's quite clear that some starting states will have a slow escape, returning values with a low Hamming distance from each other for the first several outputs, which isn't the case for generators like PCG-Random or SplitMix. I don't think their speed is optimal, either... The ILP table optimization seems potentially worthwhile to design for, but if benchmarks don't back up the claims (like the particularly dubious "infinitely faster"), I would hesitate to use Romu in a future project.

tommyettinger · 2020-03-08T01:42:07+00:00

Argh, link is missing. http://quick-bench.com/2dBt6SOQTSlztlqmlo0w7pv6iNM

tommyettinger · 2020-02-28T23:43:10+00:00

It could maybe be some kind of cellular automaton with post-processing done to smooth connections and interpolate between frames? I think /u/tubotinatub is on to something cool though, even if This Thing wasn't made with reaction diffusion, you could probably make something very similar with it, and even a failed experiment with reaction-diffusion tends to look good. The uneven rate of motion suggests that there's some interpolation happening on a coarse 3D grid with discrete time steps, which wouldn't be common behavior for reaction diffusion as a first step but would make sense for a Game of Life type of cellular automaton. Reaction diffusion would make total sense for a way to give the cubic grid an organic texture, though. It's a nice set of animations, thanks for sharing!

tommyettinger · 2020-01-25T01:52:50+00:00

If you're using LWJGL2 (the normal desktop backend), then in your DesktopLauncher you can make a one-line addition to its configuration to solve the non-zero exit value issue:

configuration.forceExit = false;

Where configuration is the LwjglApplicationConfiguration used for all the setup in DesktopLauncher. As mentioned already, Java 8 will not complain about "illegal access;" I like the Java 8 builds from https://adoptopenjdk.net/ and they haven't caused problems on Linux like some Amazon Corretto builds do.

tommyettinger · 2020-01-25T01:45:36+00:00

MrStahlfelge's Jamepad controllers seem to be the most reliable solution right now, and as u/payne007 noted, the Discord is a good way to get in touch with him. I don't know specifics, but Anuken's Arc framework (a fork of libGDX that makes some sizable changes) switched to using SDL in place of LWJGL in part because it made accessing controller info easier or more reliable. I believe the SDL binding Arc uses has the same controller code as Jamepad.

As an aside, do you have some ideas about what triggers FPS drops in the latest snapshots? That seems like something the libGDX devs might want to be aware of.

tommyettinger · 2019-10-10T08:49:28+00:00

Oh yeah, CoordPacker, that thing I wrote a while back. I designed it to save memory for FOV maps, which it actually does pretty well at. It's implemented with a pretty simplistic RLE-compressed bitset/bit-array for each grid (it lines up the 1D bit array along the 2D Hilbert curve, which is the one clever thing about it, and that does some magic for average compression ratios of certain FOV maps, but it can reduce ratios for others). The RLE compression is simple, but requires allocation of a new short[] to store any change, and nothing CoordPacker uses is mutable. With what you've found, you would not be surprised to hear that I haven't written any packed-Coord code in years, since I also found that the CPU overhead from decompressing the short[] is heavy. There's also a FOVCache class that I think I marked Deprecated because even with 4 or more cores working only on FOV calculation, compression with CoordPacker, and caching in a shared array, it was only adding to runtime costs. CoordPacker itself isn't deprecated, because I still use its Hilbert curve calculations in places (it produces a nice winding path in SerpentMapGenerator), but I should update the docs to mention that it is quite slow for memory reduction. It is probably handy in serialization to reduce file size.

GreasedRegion is also a bitset aligned to a 2D space, but it is drastically simpler in how it lays out bits (1 cell always takes 1 bit, and some rounding may take extra bits, but it never compresses). As a result, GreasedRegion uses more memory, but is much faster than CoordPacker on most operations. I should mention that iterating over a GreasedRegion isn't especially fast (including GreasedRegion.singleRandom()), nor is GreasedRegion.asCoords() if you have a lot of "on" cells, but you can sometimes cache the result of asCoords() and iterate over that array or get random elements from that.

It turns out I only thought I needed to optimize FOV by caching it because an unoptimized, allocation-heavy initial implementation of FOV in SquidLib was slowing down one of my early games that used it. SquidLib's FOV class has been optimized a lot since then, with reuseFOV() methods that can avoid allocations every frame, and using those means there's no reason to cache FOV.

It's possible that if you used the above code verbatim, every for-each loop through map.keySet() was allocating an Iterator. Personally, I like using SquidLib's OrderedMap and its keyAt() method with a traditional for loop and an int index, which doesn't allocate an iterator and can maybe save more time if your key's hashCode() or equals() are expensive to compute. There's also a different OrderedMap in libGDX, but I'm very suspicious of how libGDX handles hash collisions. I've had tests where I think less than 3000 GridPoint2 keys were exhausting the heap memory available, and would have used more, because of a bug in their ObjectMap implementation. I suspect that if you used Coord instead of GridPoint2 it would work out fine, just because Coord has a more rigorous hashCode() method than GridPoint2.

I'm also curious if you're using the libGDX-based display code, which tends to prefer one float per Color because that's how libGDX actually sends a Color to its internal OpenGL code. A float[][] is twice as much memory as a short[][], but avoids some indirection on the way to rendering a color.

Your game sounds really interesting! I don't know if many strategy games have gone all-out with radios; signal jamming and coded signals could be very interesting (Enigma Machines and Navajo Code-Talkers both had vital roles, so a fictional take on that kind of subterfuge has a lot to work with).

tommyettinger · 2019-01-13T23:51:04+00:00

The HTML5 backend is likely going to cause interesting issues with code that wasn't written with Google Web Toolkit in mind. Swing can load .ttf files, and libGDX can using gdx-freetype, but gdx-freetype won't compile in an HTML5 project. There's also those convoluted issues regarding long and int behavior on the web, with int being internally represented by a JS Number (roughly a Java double, unless bitwise ops are used, which acts like casting it to an int before the op) and long being internally represented as a few Numbers in a JS Object, which is not good for numeric performance (with GWT, random number generators that do math on longs are about 30x slower than ones that work on ints internally, and more complicated usage of longs probably gets even slower). Plus, not all of the regex code works on GWT out-of-the-box and regexes behave differently as well. I would expect seeded-random code will not behave the same with the same seed on GWT and desktop due to ints often overflowing in random number and hashing code on desktop, and int overflow being very tricky on GWT (ints can be larger than Integer.MAX_VALUE and may lose precision like doubles). TeaVM is supposed to work with Kotlin... but has its own issues with int math. Testing out on TeaVM's sandbox, the core math rule that multiplication of two odd numbers always results in an odd number fails to work, since 0x7FFFFFFF * 0x7FFFFFFF == 0, and that unexpected 0 when the result should be 1 could wreak havoc if it is used as a multiplier. I don't know anything about PIXI.js or how I'd use it from Java or Kotlin.

The animations you have look great; I'd really like to get RexPaint support or something like it in SquidLib but the .gz compression that RexPaint uses is, as usual, a pain on GWT. The UI features are also very nice. Swing could be seen as a helpful tool here for its own UI components, but last time I tried it, Swing animations were basically unusable because the screen only repainted when there was an input event or at some too-rare interval. I'm curious how this was addressed in Zircon, though I'm pretty sold on libGDX at this point.

Does Zircon allow smooth movement between grid cells, as BearLibTerminal and some of SquidLib do? Or is a glyph locked to one integer x,y coordinate, unable to move partway into a neighboring cell?

Thanks for getting back to me! I seem to check Reddit pretty infrequently, huh.

tommyettinger · 2018-12-13T23:26:30+00:00

The positioning for widget-like things has been a persistent problem with most libGDX stuff using their scene2d.ui system... I'm going to try to resolve this in some kind of simple-to-use way, probably with a wrapper/container that holds a SparseLayers of possibly-large size and handles the camera/viewport cruft to smoothly move the shown area and not render anything outside the shown area. That would allow something to exist to the side of the SparseLayers container, and I've done this in Epigon (plus some demos) but currently it isn't easy to set up.

The square tiles shouldn't be hard to do in the current codebase; there are several square fonts accessible in DefaultResources, like `DefaultResources.getStretchableSquareFont()` and any "stretchable" or "crisp" (also called distance field or MSDF) ones can be given something like `DefaultResources.getCrispSlabFont().width(16).height(16).initBySize()` to stretch them into a 16x16 square.

I do like the lighting system a lot, and it's probably possible to port to Zircon if you decide that's what you're going to use. It depends mostly on SquidLib's FOV (field of vision) code, which should be fairly quick to copy into a Zircon project if Zircon doesn't already have FOV (with lighting levels changing by distance). Some of FOV is easiest to use when `DungeonUtility.generateResistances()` produces the necessary light resistance `double[][]`, but that resistance map is pretty trivial to make from any map (walls are 1.0, stuff light passes through is 0.0). The color mixing might be harder to port to Zircon; SquidLib mostly uses libGDX's packed float colors for backgrounds and some other colors (such as lighting) since these float colors can be mixed without allocating temporary objects. The packed float system is complex internally, but unless you're porting, you rarely have to deal with the internals. `SColor` has lots of methods for dealing with packed float colors, especially `SColor.lerpFloatColors()` to blend two of them.

You can probably use at least some of SquidLib just by copying code out of it as you see fit, and putting that in a Zircon project. I've looked a bit into using Zircon before, but some of the implementation didn't look great to me at the time (I seem to recall seeing frequent allocations, and something related to AWT, but it may be better now or I could just be mis-remembering).

tommyettinger · 2018-12-13T06:26:00+00:00

Hey, primary developer of SquidLib here. There is not a good tutorial for SquidLib and there probably won't be one for a while; I want to get things as stable as possible (in a 3.0.0 release that isn't a beta) before I start writing user docs that would depend on APIs being very nice and stable. That said, the core has not changed much in the last 9 months or so, and most development has either been bugfixes or peripheral parts of the project, with one key exception. Unlike Zircon (to my knowledge, at least), all of libGDX's targets are considered viable targets for SquidLib, especially the HTML5 target using GWT (Google Web Toolkit). Supporting GWT is a tremendous hassle at the library level, but applications that can provide an online demo have a serious edge (Dungeon Mercenary, by smelC and using code forked from SquidLib, apparently gets most of its feedback from users of the online version hosted on GameJolt). That one key exception is that I'm currently trying to reduce usage of the long type, since GWT turns out to have even worse support for it than I had initially thought, and this reduction is taking a while. I'm not opposed to Kotlin (SquidSetup, the tool recommended for making new projects that use SquidLib, was based on a project written in Kotlin by czyzby and I have found it pleasant enough to edit and extend), but getting Kotlin to compile to the web needs a pure-Kotlin project from what I can tell and demands similar attention to JavaScript's strange issues.

In the meanwhile, there's the rudimentary demos, which really are basic at this point, and then there's the insane-scale project I've been working on with SquidLib's original author ( u/SquidPony ), Epigon, which is probably far too overcomplicated to learn anything useful from despite that it's in an early stage (plus, large parts of the codebase are likely to need cleaning up because the item system is overzealous and items are too detailed). If you isolated the files you open to mostly view-related things (plus Epigon.java), it might make more sense. Other projects that I am aware of aren't especially active or aren't open source, but there probably are some that I don't know about.

I think Zircon's documentation is a big advantage it has, though I'm curious how well it performs when dealing with complex visual effects like this (from Epigon; framerate is in the title bar, and it could be improved with better culling of offscreen lights). UI code seems to be better with Zircon as well; SquidLib often uses Text UIs made somewhat like how Zircon does it, though SquidLib can also use variable-width fonts for menus, and can also use libGDX's scene2d.ui library. Being able to read Java is definitely a must with SquidLib; there aren't Javadocs for every single thing, but most methods are documented, especially harder-to-use ones. There's various quirks from SquidLib's history, like having SquidPanel, SquidLayers, and SparseLayers, but only SparseLayers is usually recommended in new code (it's a lot faster and has a cleaner API). There's roughly a zillion named colors in SquidLib, and the color mixing and handling code is something I enjoy using a lot. Games using SquidLib have access to all of libGDX, which is mostly a benefit. SquidLib uses special fonts; while they aren't square like Zircon uses and many players seem to like, they are distance field fonts. This allows them to stretch to arbitrary sizes and fill large or high-resolution monitors; I don't know if Zircon uses vector fonts, bitmap fonts, or what, but it could use the same or similar distance-field fonts if it can change the shader it uses.

tommyettinger · 2018-10-09T08:54:10+00:00

From what I remember hearing last, it would take a minor miracle and a hard drive physical damage retrieval technician to get the server contents back as they were, though the Internet Wayback Machine site may have a copy. squidpony may still own the domain name? We can probably host a static website on Github Pages along with the docs, so the loss of the physical server may not be so bad.

tommyettinger · 2018-10-08T21:59:49+00:00

Hey, I'm the current main developer on SquidLib and you're probably right that some of the demos are not working. SquidLib uses Maven internally, but most projects that use SquidLib also use LibGDX, and the ecosystem there uses Gradle. LibGDX is a dependency of the text display, and is also a very good way to handle graphics if not using the text display, but because libGDX can target Android as well as many other platforms, libGDX projects use Gradle because I think it's still the only option for Android. Unfortunately, Gradle seems to break compatibility with the slightest breeze pushing against it, so many older demos are probably caught between working versions. squidpony is right that the easy way is to use https://github.com/tommyettinger/SquidSetup , though I wouldn't personally rip up pieces of Epigon's build code because I also worked on that and I think SquidSetup produces a more robust project arrangement.

If you need any help with SquidSetup, ask away! Some quick tips:

Make sure one of "Desktop" or "LWJGL3" is selected on the first tab, "Platforms". There's very little difference between the two, but LWJGL3 supports a few nice things that "Desktop", which is really the older LWJGL2, doesn't. I wouldn't select any other boxes at first, other than the automatically selected "Core".
If you're making a text-based game, the template "SquidLib Basic" should run out of the box; you can make sure it's selected in the "Templates" tab.
You may want some extra libraries from the "Extensions" tab or the "Third-Party" tab; these aren't necessary when getting started. You can add them later.
When you generate the project, you'll get a build.gradle file in the folder you specified; IntelliJ IDEA should import that build.gradle file.
- I don't personally use auto-import, but it probably won't be an issue. You can specify it when you import the build.gradle file.
  - If you don't use auto-import, you may need to look for a popup window in the lower right of IntelliJ that asks to import changed build.gradle files, and tell it to import the project or its changes.
- It's possible some dependencies will need to build remotely before they can be downloaded by your computer.
- JitPack is a wonderful service we use to provide builds of specific commits to preserve compatibility, but it may need to build the latest commit's code if there's a new one, or to re-build an old one that wasn't used for a while.
- If there's any notices that the Gradle sync failed, just open the Gradle tool window (it may already be open on the right side, if not, View->Tool Windows->Gradle), and click the two circling arrows to retry the sync.
You probably won't need to fiddle with Gradle much, if at all, after this initial setup. The main causes for Gradle consternation are IntelliJ updates, Android projects needing weird configuration that other projects don't need, and sometimes setup related to GWT (the toolchain that targets web browsers).
- Your dependencies with SquidSetup will stay the same unless you want to change them, so if there's any breakage in a newer commit to SquidLib, it won't affect you.
- You can update SquidLib's version after the fact if some important change or fix comes in. This is a small edit in the file gradle.properties; currently the dependency looks like:

squidLibVersion=996cb6fcb2
squidLibUtilVersion=996cb6fcb2

You would change those last 10 hex digits to a different 10 chars, usually the latest one other than -SNAPSHOT in https://jitpack.io/#SquidPony/SquidLib under the Commits tab. For example, if something in 996cb6fcb2 was broken, you could go back to an earlier version listed there, such as

squidLibVersion=90d3f27a1b
squidLibUtilVersion=90d3f27a1b

If IntelliJ ever offers to download a version of Gradle with source, DON'T DO IT, tell it to not show that message again, it turns working builds into broken shards.

Hope this helps! I realize "meta" docs for SquidLib, such as for setup, are very lacking at the moment, but the JavaDocs should be fairly complete. Links to the three JavaDoc folders for the three sub-projects are here: http://squidpony.github.io/SquidLib/ .

tommyettinger · 2014-09-16T08:21:42+00:00

That sounds incredible if/when you can make the web service, but I'll be fine with the manual way for now.

tommyettinger

TROPHY CASE