Algorithms...

Slightly offtopic, but here is an algorithm I am not proud of at all. Too long, too nested, too much hackery, too many magic numbers...



But I'm proud this is the only awful method in my game ;)

I spent about 8 months at my last job redesigning their core document management system. Before I came along they had to spend about a day of custom coding and database updates for each new client. Now everything is completely automated and new client's document types are generated based on their location and possibly previous or other clients who would have similar document types. That probably doesnt make much sense to anyone, but I'm damn proud of it :) And at the core it was really just one huge algorithm, so I think it qualifies for this thread.

Now the real challenge is trying to find a concise but impressive 20 word way to describe the whole thing so I can put it on my resume :(

An algorithm that enumerates Razz(poker) hands around 1000x quicker than anything on the market!

I approached the problem from an entirely different angle, and came up with a solution in around 2 weeks of thinking every day for around 6-8 hours. The application surrounding the algorithm will be ready in a few months.

I created a (audio)graph lib-like thingy some time ago with which you could connect filter-classes together using pin (also a class).
I wrote a templated class for that in C++ that could check at runtime if two pin types could be connected without any conversion-> ie, if the types were interchangable or implicitly castable.
And I was this, this --><--, close to not needing any RTTI at all to do it (only used RTTI to do a lookup, didn't do the cast itself), but they stopped the project :-(
This was the first time I did any template meta programming in C++ and I was pretty proud of myself that I understood the concepts well enough to write that class.

And my lib that can do object synchronization and method calls over the network in C# is pretty neat too.

A defragmentation routine to replace the default methods used on a very large game project a couple years back. I called it the "Super Scooper" and it may be an idea which already exists, but essentially the problem is you have this list of fragmented memory. You know how much space you need to free up to make an allocation and you want to achieve that (or better) by moving the least amount of memory.

Some methods act like a sorting from top to bottom where it moves free memory to the top or bottom until there is enough free to give an example. Each algorithm was tested if the previous one didn't involve only a single move. So it would virtually run each algorithm before actually shuffling memory to avoid the much more expensive operation of actually moving anything.

What I did is create an algorithm which would seek the largest two open spots separated by the smallest used spot and then attempt to move that used spot elsewhere. In this way we "scoop" the memory out of the way from between two empty blocks. It proved to be quite efficient and was actually used as the default memory defragmentation routine. This algorithm was also recursive as all of the others were, so each step it would repeat this action.

The term "super scooper" which relates to picking up dog crap and moving it to the appropriate location seemed to fit.

If anyone recognizes this algorithm as an existing one let me know, if not and you use it, mention my website and name: Michael Hamilton, mutedvision.net

Quote:

Original post by M2tM A defragmentation routine to replace the default methods used on a very large game project a couple years back. I called it the "Super Scooper" and it may be an idea which already exists, but essentially the problem is you have this list of fragmented memory. You know how much space you need to free up to make an allocation and you want to achieve that (or better) by moving the least amount of memory. Some methods act like a sorting from top to bottom where it moves free memory to the top or bottom until there is enough free to give an example. Each algorithm was tested if the previous one didn't involve only a single move. So it would virtually run each algorithm before actually shuffling memory to avoid the much more expensive operation of actually moving anything. What I did is create an algorithm which would seek the largest two open spots separated by the smallest used spot and then attempt to move that used spot elsewhere. In this way we "scoop" the memory out of the way from between two empty blocks. It proved to be quite efficient and was actually used as the default memory defragmentation routine. This algorithm was also recursive as all of the others were, so each step it would repeat this action. The term "super scooper" which relates to picking up dog crap and moving it to the appropriate location seemed to fit. If anyone recognizes this algorithm as an existing one let me know, if not and you use it, mention my website and name: Michael Hamilton, mutedvision.net

Wow damn nice man! If I implement it I'll give you full credits...

I did something for my project in my Compilers course. First, some basic knowledge: inferring ML types on recursive functions in a polymorphic manner is not computable. Meaning that you can't write something like:

type 'a evil_tree =   | Node of ('a * 'a) evil_tree  | Leaf of 'alet evil_tree = Node (Node (Leaf ((0,1),(2,3))))let rec apply f = function  | Leaf x -> f x  | Node x -> apply (fun (a,b) -> f a ; f b) x

In theory, the type of apply here would be ('a -> unit) -> 'a evil_tree -> unit. However, since Hindley-Milner inference is monomorphic on such functions, it will attempt to unify 'a with 'a * 'a and fail. Recursive types don't help either, by the way, since 'a is not a recursive type (evil_tree is).

In the small ML-like language I had designed for the project, I used an alternate type-inference algorithm which attempted polymorphic inference on recursive functions. A problem being non-computable means that, for any program that tries to solve it, there's at least one question for which the program will loop forever or give an incorrect answer. The trick I used was to design the algorithm such that:

1. If a correct type existed, it would be inferred in finite time (meaning that when a type did not exist and the program would sometimes loop forever).
   
   
2. The algorithm could determine at any point in time that, if a result existed, it would be larger than a certain size (in terms of nodes in the ML type tree).

Since I don't expect a normal programmer to create functions with types that are greater than an arbitrary fixed constant (say, more than 1024 nodes in the type tree) I rigged the algorithm to stop as soon as that treshold was exceeded. This meant that incorrectly typed programs were detected as such, correctly typed programs with types smaller than 1024 nodes were detected as such, and correctly typed programs with types larger than 1024 nodes were erroneously detected as incorrectly typed. Making the 1024 a compiler flag meant the programmer could always tweak the value if it became necessary.

That thing. I made various stuff ever since but nothing that I was this proud of.

Quote:

Original post by Lovens Wow damn nice man! If I implement it I'll give you full credits...

Thanks, glad you thought it was neat. Yeah, just shoot me an e-mail so I know what project is using it too, it may be useful in a name-drop if it is a bigger project and I say "xxx project and xxx project are using an idea I came up with for defragmentation" in an interview. I'm saying this because I notice it looks like you work for a game studio and that would rock (though it may not be, not really sure what Hypergames is) ;) maxmike@gmail.com

Dmytry, that is a damn cool erosion fractal program.

ToohrVyk I think that would mean more to me if I had ever written a compiler. It sounds like you solved an infinite problem by adding a cap to the number of checks which is practical but not graceful. There may be no graceful solution though. I'd have to know more about the problem domain to comment.

Quote:

Original post by M2tM ToohrVyk I think that would mean more to me if I had ever written a compiler. It sounds like you solved an infinite problem by adding a cap to the number of checks which is practical but not graceful. There may be no graceful solution though. I'd have to know more about the problem domain to comment.

The elegant part was not capping—it was to design the algorithm in such a way that it allowed capping.

We (well mostly a guy I hired) came up with a way to do fake solid geometry slicing on arbitrarily complex 3D models.

Quote:

Original post by ToohrVyk Quote: Original post by M2tM ToohrVyk I think that would mean more to me if I had ever written a compiler. It sounds like you solved an infinite problem by adding a cap to the number of checks which is practical but not graceful. There may be no graceful solution though. I'd have to know more about the problem domain to comment. The elegant part was not capping—it was to design the algorithm in such a way that it allowed capping.

That actually clarifies what to look for in your explanation. I see now :)

when i was young i invented way to speed up DFT calculations
years later i found out in a book that it has been already invented and called FFT.

Years ago, before 3D cards came out, I wrote a software 3D engine in the days of MS-DOS. The z-buffer was taking up a ton of CPU cycles I couldn't afford, so I investigated the s-buffer approach. I was only about 13 at the time and it was the first time I ever attempted a proper algorithm. I read the basic idea and actually wrote the entire algorithm on paper in pseudo-code before starting.

Amazingly (to me) it worked great. Although I lost the code so I will luckily never have to see how horribly ugly it no doubt was.

Quote:

Original post by Dmytry That thing. I made various stuff ever since but nothing that I was this proud of.

Hé, I remember that one :) Didn't you say you'd post more explanations on the algorithm btw ? That was already a few years ago, maybe I missed it.. or did you want to patent it ?

Y.

I was working on a problem that was basically subset selection, which is O(n^2). On each subset, I was running a least-squares solution and testing whether the solution 'fit' my model or not. It was extremely slow, because every time a new point was added, I had to do the whole process over.

I realized that I could memoize results (so I didn't have to recompute every frame), and then sort points (since it was a time series) such that if the least squares model didn't work on (A, B, C), it wouldn't work on (A, B, C, D). This gave me the ability to create a rather elegant recursive solution that was also very efficient.

Here is a quick skeleton of the algorithm.

Original post by M2tM

Quote:

Original post by Lovens *** snip *** Thanks, glad you thought it was neat. Yeah, just shoot me an e-mail so I know what project is using it too, it may be useful in a name-drop if it is a bigger project and I say "xxx project and xxx project are using an idea I came up with for defragmentation" in an interview. I'm saying this because I notice it looks like you work for a game studio and that would rock (though it may not be, not really sure what Hypergames is) ;) maxmike@gmail.com

HyperGames is NOT a game studio. It's a game dev team.. We are working on a 2D-3D platformer and this week, if my girlfriend lets me work, I'll develop my next new algorithm: Weche Algorithm For 24bit Color Maximization :-) Hope it gives good results!

I wrote a function that could recreate portions of XML documents based on assumptions about XPath queries that were intended to be valid. It was a way to very quickly generate XML documents that conformed to a specific schema with very few actual edit calls.

Quote:

Original post by Dmytry That thing. I made various stuff ever since but nothing that I was this proud of.

I remember this, it really impressed me when I stumbled upon the page, I would be greatly interested in any further details :)