Matt Downey @SciFiGameDev@mastodon.gamedev.place

Finished my 6-second game trailer for my Asteroids (1979)-clone in virtual reality:

https://youtu.be/tGoc2T6ABUc

One of these days I will get a job.

I would allow ~15 tags, which are used in tag searches (which like the standard front page have rankings).

When doing an arbitrary search, the results would alternate results on 1) comparison by title 2) comparison by summary and 3) comparison by tags.

Bots and bad actors would still be a problem, of course, but it would be interesting to see how the community/ecosystem worked.

I think I finally figured out how I would do egalitarian ranking on the internet.

Only include a concept of downvoting. Scores are in a range of [0, - infinity). Rank them according to highest scores first and ties go to the most recent.

One year after an item is downvoted, the downvote is removed (and the same person cannot downvote the same thing).

No recommended / related items. Ranking only used for the front pages. Search is egalitarian based on search relevance (open-source algorithm).

Perhaps the biggest obstacle that's presented itself is how to make the story either optimistic/philanthropic or, perhaps, neutral.

Even when the game was impersonal, it was an allegory for an abusive relationship (despite having never been in a relationship), and when I got really depressed in 2017 I wanted to make the game way more depressing.

The nice thing about games is you can change them, so with any luck it'll be creatively redesigned into something better several years from now.

I was under the impression more experience building games (other than the one I crave to build) would make Invertigo better, but I don't think that's fully true.

Yes, practical experience helps, but if I want to make something that expresses who I am, I shouldn't make something that is practice worldbuilding.

Sure, I strive for perfection (and fail all the time) so it makes some sense to save Invertigo for later, but I think it's a more honest rendition of my self to release an imperfect game.

I'm wondering what I want to do next.

Converting 2D games to virtual reality would work out okay, but it makes more sense to work on the game I have been developing from the beginning, Invertigo.

You only get to make so many games in life, so I should be pouring my soul into my games and not procrastinating by porting other people's games into virtual reality.

Some programmers know about the `-->` ("goes to") operator, but how many programmers know about the `^0^` ("excite") operator?

I just got the prototype done for converting any 2D game into a 2D virtual reality game. ^^

I think it works pretty well (I tested it with a screenshot from a popular game).

Took me all of two hours, about as long as expected, although there's more to do (including a bugfix).

The algorithm would probably perform better if the Build-Heap operations were interlaced.

One possible good idea that came out of this is an alternative to insertion sort when the quicksort size gets small.

You can theoretically do for e.g. 255 values:

Build-Min-Heap(1...255)
Build-Reversed-Max-Heap(128...255)
Insertion-Sort(1...255)

I don't know how useful it would be in practice, but I think it would have better branch prediction.

Maybe the best / most useful strategy is the one that requires the least overhead. I often overengineer things; maybe I should stop that mentality.

=/

I think I should probably just go back to binary heaps, then, since they should provide the same asymptotic performance.

It seems I was equal parts bad-at-statistics, overly-optimistic, and bad-at-reading here.

Also, apparently information theory say n*log_2(n) is the best you can do in the average case.

I probably should have checked the lower bound of comparison sorts a long time ago.

This means I should go back to the original goal (exclusively): try to make an algorithm that performs between O(n) and O(n*log_2(n)) depending on whether or not the data is sorted, nearly sorted, or random noise.

On second thought, I don't think this Build-Heap operation would be as useful as a Leonardo Heap.

There should be plenty of long sequences where you are basically doing Bubble sort (which does not work well with reverse-sorted-order).

If I were more statistically-minded I might be able to find a good structure on my own, but I'll just trust other more-experienced computer scientists like Dijkstra here.

Oh wait, you would still need to create a binary heap or Leonardo heap to have any guarantees on the elements you're removing being sorted.

Worst case, you can imagine putting elements in reverse sorted order and it still runs into situations where only one node can be upgraded.

Thus you would have to do one iteration of Bubble sort on the entire heap or build a heap with guarantees.

Additionally, with this hypothetical pidgeonhole heap, I think building in both directions simultaneously to prevent the rogue 4th value problem is almost a necessity.

This does mean you get to remove sorted values from both ends and your partition line becomes better so it's probably not as bad as 2*2.6n comparisons/swaps per iteration might imply.

I wish I could know if these ideas could work before I program them.

Ultimately, I want to try to improve 1) sorting for nearly-sorted data and 2) if possible, get an expected sorting time better than Theta(nlog_2(n)), even if that means Theta(nlog_2(n) / log(log(log(n)))).

This concept is far from perfect, but I think it should accelerate / catalyze pushing values into sorted order.

The problem is that some values are stuck (e.g. 4), which is why you would absolutely need to alternate directions.

I also don't know precisely how to remove sorted elements from the head of the list without accidentally including inversions. I think it's as easy as before, but I'm not certain.

The next question becomes, "How do you Heapify / Build-Heap?"

If you had e.g. 34 elements, you would compare the 34 items bottom to top with their parent and swap if necessary. Then you would do the same with 21 elements, then 13, then 8, then 5, then 3... 2, ... 1

This means (and I think I checked this correctly) the Build-Heap operation should occur in something like 2.6n iterations.

Some "gap" comparisons (e.g. 4) never need to be checked again.

An example of a pigeonhole (Fibonacci) heap lookup table:

These parents determine comparisons.

0th node has parent of 0
1 -> (points to) 0
2 -> 1
3 -> 2
... 4 aka 3+1 -> 3
5 -> 3
... 6 aka 5+1 -> 5
... 7 aka 5+2 -> 6
8 -> 5
... 9 aka 8+1 -> 8
... 10 aka 8+2 -> 9
... 11 aka 8+3 -> 10
... ... 12 aka 8+3+1 -> 11
13 -> 8
... 14 aka 13+1 -> 13
... 15 aka 13+2 -> 14
... 16 aka 13+3 -> 15
... ... 17 aka 13+3+1 -> 16
... 18 aka 13+5 -> 16