Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.


Messages - harold

Pages: 1 2 3 [4] 5 6 ... 16
46
Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 03:31:21 pm »
The weird thing with those is, that if you "tick" every block in a chunk in the same order (0/0/0),(0/0/1),...,(0/1/0),...(15/15/15). you can see "invalid" states.
As calculation doesn't happen parallel to rendering (that'd be horrible, both usability- and code-wise), (15/15/15) can react to a change of (15/15/14) in the same tick. Minecraft does it a bit differently: Only a few blocks of each chunk are "tick"ed each frame. They're chosen randomly, so you get such states very seldom. It can cause horrible bugs, though.. I also thought about a game-of-life like implementation, like double-buffering. Copy the redstone state of the chunk before doing ticks and only after every block recalculated itself, make the new state the current one.
I'm using the "fill a new buffer, then make it the current one" approach now. I'm not sure how the repeater locking enigma interacts with this. I still don't see how this makes sense though:

Especially not since that appears to happen consistently.
But then you add an other repeater, and suddenly:


Quote
I get 1000000 (cubes) * 6 (faces) * 4 (vertices) * 5 (x/y/z/u/v) * 4 (bytes in a float) ~= 500 MiB and that's EVERYTHING. In the ultimate WORST case.
I put a bit more in there (normal, texture array index, stuff to paint redstone dust directly onto it, which might be a bit wasteful perhaps), comes out at 48 bytes per vertex, just over 1GB for a million cubes. But that's all just a factor of 2 anyway, make it 2 million cubes and you have the same problem again.

Quote
This looks interesting. Do you also plan on creating a .scematic exporter so that you can paste anything you make in a real minecraft world?
Maybe. They're not entirely compatible though, only roughly in the same ballpark. There are, and probably always will be, slight differences that would break some circuits if you took them from this to MC or back.

47
Computer Projects and Ideas / Re: Redstone-oriented Minecraft clone
« on: August 23, 2014, 02:40:46 pm »
Redstone (and repeaters) on walls, ceilings, torches on ceilings as well? That'd be very useful :D
All of that could be done. Isn't it a bit of a cheat though? Ah well I'll see.
Quote
A nice feature would be to save "patterns" like gatters or special configurations and the ability to place them down wherever you like and in every orientation.
Good idea

Quote
Quote
Some redstone logic already works to some degree, for example:
 - torches, both floor-mounted and wall-mounted. Don't burn out though, and I'm not sure whether to make them burn out. They also react to 1 tick pulses, which is wrong. (that's how the above screenshot has 1 tick pulses)
Why is this wrong?
Uhm, I guess it isn't. I'm not sure how that's supposed to work tbh. Aren't torches supposed to ignore 1-tick pulses? Why else are "1 tick torch transmission" things so "special"? Then again, that circuit was always a 1 tick clock IIRC.

Quote
"time travel"? Weird data dependancies? Or have I forgotten how they work? AFAIK it's only that the repeater doesn't change state if it's powered from the side.
Yea normally it's simple, but for example if you power a repeater at the same time you power the lock, it gets locked in OFF state, even though at that point it is not powered from the side yet. It gets worse if you add an other repeater that simultaneously tries to lock the lock. Please tell me you know how that works..

Quote
How did you implement this [redstone dust]? Minecraft does it exactly how I do it in crafti: Connected redstone dust is treated like a single thing and updated at once (for timing and loop-avoiding purposes)
Basically I floodfill through it starting from active power supplies.

Quote
If you have chunks (exactly like minecraft) anyway, why not make the map infinite?
Well right now, I'd run out of coordinate space. I could use a wider type there I guess. Also because of the way I did it, I'd run out of floating point resolution relatively quickly if you go much further from the origin than you can now, I'd have to throw in some more trickery to avoid that. Might happen.

Quote
Quote
However, naively, if a redstone signal changes, that means a change in a chunk because you'd have to update some texture coordinates and that means reuploading the geometry, this time with different texture coordinates. That would make far too many chunks be reuploaded, so to counter that, I've decoupled powerlevels from geometry
Powerlevels don't have to be sent to the GPU. If you mean the color of the redstone wire/dust, that's IMHO unnecessary complexity. GPUs and DMA are fast enough, so if you use VBOs, everything should be fine without these optimizations. Did you do any performance tests?
Oh it was fine .. on a small enough or sparse enough map. If 1 million cubes is small to you, this will never be good enough. 1 million cubes is right up there with the PCIe 2.0 x16 throughput limit of 0.8GB per update (assuming 10Hz), actually slightly beyond the limit. Of course that case would only be hit if all chunks changed and they were all in the frustum, but that's not something that's completely impossible. Now this will not be a problem again (unless I put in pistons).

48
Computer Projects and Ideas / Redstone-oriented Minecraft clone
« on: August 22, 2014, 08:29:54 am »
You may have seen a couple of screenshots of this appear on IRC, at the time of writing it looks like this:

They're pulse circuits, so it looks like a bunch of things are incorrect but that's just because of their delay.

Anyway, the goal as I set it for this project is to be able to build/test/run redstone circuits without various minecraft annoyances, most of which can be fixed with mods I suppose..
Basically it's creative mode on steroids. Nothing that distracts from just building circuits. World-edit-like godmode editing. And I have some plans for putting in things like displaying delays and critical paths and some automated circuit testing stuff (such as cycling through a bunch of different inputs without having to build a circuit to do it). None of that exists just yet, I'm just doing the basics now. Also, the ability to pauze, step, fast-forward redstone simulation.

Some redstone logic already works to some degree, for example:
 - torches, both floor-mounted and wall-mounted. Don't burn out though, and I'm not sure whether to make them burn out. They also react to 1 tick pulses, which is wrong. (that's how the above screenshot has 1 tick pulses)
 - repeaters. You may have hear me complain about them. A normal 1-tick repeater that isn't locked works fine. Other delays may or may not do what they're supposed to do, the screenshot above is testing how they respond to 1 tick pulses and they respond correctly. I'm not sure about other inputs though. Also, locks make no sense and are currently incorrect (correct behaviour requires time travel).
 - redstone dust, I think, works correctly in terms of which blocks it powers, what it looks like (apart from the particle effect), how far signals travel, and signals don't go down transparent diodes.
Some things are not there but will be there soon:
 - comparators
 - editing (it just loads and simulates now)
Some things may or may not ever be included:
 - pistons (I know you like them, but they suck to simulate, and I'm sure you remember how long they caused trouble in MC)
 - shadows / lightlevels would be pretty, but not useful and would slow down rendering, particularly of complex+big maps.

Trickery used
The world can get pretty big (256x256x256 at least, it should work with 1024x1024x512 as well but not tested), which is smaller than "real minecraft", but still brings some challenges.
For example, it's impossible in general to reupload all geometry every frame, or you'd have maybe 1 frame per second. In order to avoid having to reupload too much stuff that wasn't changed, the world is divided in 16x16x16 chunk. Chunks with no changes are left alone. However, naively, if a redstone signal changes, that means a change in a chunk because you'd have to update some texture coordinates and that means reuploading the geometry, this time with different texture coordinates. That would make far too many chunks be reuploaded, so to counter that, I've decoupled powerlevels from geometry, so I can update them separately with only a tiny upload of only 2kb (16x16x16/2 because power levels can be packed in nibbles) versus about 1kb per solid block (minus faces that touch other solid blocks) in the chunk. It's a bad deal only if there are 1 or 2 blocks in a chunk, which is not the common case.
The powerlevel data is also used by "objects" (torches, repeaters, etc) to determine their state, even for the lock-bar of repeaters, so as long as only redstone signals change, no geometry is reuploaded.
To avoid having to deal with "ordering" with transparent parts (torches draw some transparent parts), transparent pixels are discarded. AA tends not to like that, but it works in combination with sample shading.
Possible future trickery: if I can figure out how to do it well, maybe fuse some faces and use texture wrapping. That would significantly reduce the polycount in some cases, but I'd have to careful not to mess anything up. Polycount hasn't really been a problem so far though, a million randomly placed (but not multiple at the same location) solid blocks still render at 30FPS (on a HD6950, +vsync), I doubt any real build would even come close to that.

Tech used/platform
C# and OpenGL 4. The biggest compatibility obstacle is probably the extensions I used and buggy/old GPU drivers.

49
One with an Intel Atom (might be called a "netbook" due to extreme slowness).

50
Miscellaneous / Re: Press Neutrality
« on: June 09, 2014, 02:31:57 am »
It's funny, the last time such an idea was implemented (ie, press was only allowed to report truth), it was widely regarded as oppression of the press, because it means the government is telling the press what they can and cannot publish.
It's even funnier when you talk with, say, Chinese people. Turns out the strategy of using multiple sources doesn't cut it (at least not necessarily) - there is also a large amount of bias that they all share. "The West" often accuses China and the like of biased reporting, but what you don't hear is that they in turn also accuse us of it (because well, where would you hear? certainly not from the accused - which in itself shows they have a point). It's easy to think that only one of them must be right, but it's even more likely that all news everywhere is biased - there is no obvious reason for it not to be.
So really, what you need is not just multiple sources, but sources not based in the same country. Better yet, sources not based in the same alliance. For example RT and Al Jazeera, instead of just the usual "Commonwealth and US"-area sources. NK News, maybe not. I take a look sometimes, and it's interesting in its own way (you can read it for laughs), but as a news source it doesn't do much.
And even I suspect there will be news that everyone biases to roughly the same side. There's no guarantee that it averages out.

51
Update time! Added a very simple trick. It now takes about 0.4 miliseconds on the same test data (it varies between 350 and 400, most commonly 390).
That's varying between 360 to 410 MB/s, usually 370MB/s.

There's also a very easy way to make it faster: use a simpler way to encode length/distance pairs. But that would change the format a lot, and I intended to stay close to Deflate.

52
Humour and Jokes / Re: Omni meme compilation !
« on: May 18, 2014, 04:57:45 pm »
Over half of these are not specific to Omnimaga, do they still count?

53
ASM / Re: Learn Hex/NikProgrammer
« on: May 04, 2014, 02:35:15 pm »
Of course, but that's a little unspecific.

What's the trouble?

54
Math and Science / Representing disjoint sets
« on: April 02, 2014, 06:56:38 am »
None of this is new, but I think it deserves more attention.

Parent pointers. As discussed in wiki:disjoint-set_data_structure. Every element points to its parent, the root identifies the set. Singleton sets are an element that points to itself. This is a relatively well-known data structure because every CS curriculum covers it, usually in the context of amortized analysis.
It supports merging two sets in O(log n) and identifying which set an item belongs to also in O(log n), but remember the amortized analysis that makes this data structure so good.
But here are some things you don't get (without extensions), or not nicely:
  • seeing how big a set is. But you can fix that: take an extra array "size", initialize it with 1's, and on a union, do size[newroot] += size[otherroot]. Getting the size of the set containing x is just size[find(x)].
  • removing an element from a set. Other elements might be pointing to it, and you have to find them and fix them. The pointers go the wrong way, so you have to scan everything to find them.
  • a good way to enumerate some set. Again the pointers go the wrong way. You can scan through all items and see if they belong to the set, and in some ways that is not so bad (in the worst case, the set contains everything, and you'd have to visit every item anyway), but it could be better.

So here's a way that initially looks related, but is actually very different: cycles. It looks the same in that you start out with an array [0, 1, 2, 3 .. ], but the similarities pretty much end there.
A set is represented by a cycle. You follow a cycle by doing x = array[ x]. To merge to sets, take any item x from the first set and any item y from the second set, then swap array[ x] and array[ y].
Here are some diagrams to clarify:
Begin situation. Every element is in it's own cycle/set.

Merge the set {1} with the set {2}.

Merge the set {0} with the set {3}.

Merge the set {0,3} with the set {1,2}, could be done in several ways, shown here by swapping array[ 2] with array[ 3].

It should be obvious that this is reversible, so you can easily "undo" merges if you remember which two items you used in the merge.
You can also remove an item from its cycle, but that requires knowing the element which points to it. When you're iterating over a cycle, you can remember the previous element, so you can unlink elements from their set while enumerating that set.
Unlike with the first data structure, finding out which set an element is in is hard, and there's not even an indisputable representative of a set anyway. You could enumerate a set and take the biggest or smallest item as representative, though. An other trick is to add a bunch of items that are only used to "give names to sets".

But it gets better. What if you combine those two data structures?
Merging becomes O(log n), inherited from the union-find structure. There is now an indisputable representative of a set, namely the root in the union-find structure. And now you can also remove an item from its set in a more reasonable O(|S|) where S is the set containing the item (vs O(n) before), with a  very simple algorithm: if the array containing the cycles is called "cycles" and the item we're removing is "x", iterate over the cycle setting the parent pointers to cycle[ x], and when you reach the item y such that cycle[ y] = x (ie, you've completed the cycle), swap cycle[ x] and cycle[ y] to unlink the item. You can still keep track of the set sizes with no significant overhead.
So you can:
  • Merge the set containing x and the set containing y in O(log n), or O(1) if you already know that x and y are both roots
  • Determine the set containing x in O(log n)
  • Enumerate the set containing x in O(|S|)
  • Remove an item from its set (making it a singleton set) in O(|S|)
  • Get the size of the set containing x in O(log n), or O(1) if you already know that x is a root
Of course the amortized analysis of union/find with path compression still applies, so it's actually better than those O(log n)'s make it look (that already looks pretty good though).
The algorithm for removing an item from a set guarantees that find operations on any of the items in the set that you just removed an item from will run in O(1) the next time, partially off-setting the bad-looking O(|S|) time. Essentially it performs path compression on every item in the set, and in a way that's faster than usual.

As a variant of the cycle structure, you can use two arrays, containing the same cycles but with one going "backwards". Essentially emulating a doubly linked list instead of a singly linked one. Visualize it with double arrows. In this data structure, you can unlink items from their cycle in O(1) (at all times, not just if you remember the previous node), and here's an other fun trick: instead of making the unlinked item into a singleton cycle, you can keep its pointers intact. That way it remembers its original position in the cycle it came from, and you can undo a sequence of unlinkings by relinking them in reverse order. This is a reasonably well-known trick on cyclic doubly linked lists, most famously used in the Dancing Links algorithm.
There's not much point in combining this with the union-find structure, but it works well together with a plain old "array of integers saying which set an item belongs to", that's bad for merging two sets, but it becomes interesting if you're only ever shuffling single items between sets.

Here's an other trick: all the arrays can start out as all zeroes, with only small modifications to the code (and no conceptual changes to the algorithms). Instead of treating items as index of the item they refer to, treat them as an offset. You're indexing into the array, so you always know the current index, the value that you're conceptually storing is just i + array[ i]. The ranks already start at 0, and making the set sizes zero just means off-setting them by 1.

55
TI-Nspire / Re: Binary Puzzle for NSpire
« on: February 28, 2014, 01:18:53 pm »
I didn't generate them; I wrote a small executable that downloads the HTML from http://www.binarypuzzle.com/puzzles.php?size=%d&level=%d&nr=%d where the first %d is 6, 8, 10, 12, 14; the second one is 1-4; and the third one is 1-100.  And in that HTML is the puzzel as well as the solution.  I converted from that into the make-up of how this program reads in the puzzle files.
Oh, ok. I was hoping there would finally be someone that I could really talk discuss the generation of binary puzzles with. Maybe we can still do that, but it would have been interesting to compare our methods and so on.
On the 8x8 puzzles: Sure!  How many do you got?  I've been hoping somebody would make an external level for this game.
Depends on how long you want to wait. Here's some: https://dl.dropboxusercontent.com/u/27035142/level5.txt (that's about 3.5 thousand of them)
You can see by the timestamps that I'm generating them pretty quickly.

56
TI-Nspire / Re: Binary Puzzle for NSpire
« on: February 28, 2014, 01:06:28 pm »
How do you generate them?

Also, do you want to borrow some hard 8x8 instances?

57
Math and Science / Re: .9 repeating equals 1?
« on: December 11, 2013, 03:30:53 pm »
Dedekind cuts probably aren't going to convince the deniers, though. Let's be honest, they don't really make intuitive sense, and the biggest reason the deniers have is "but it doesn't make sense"..

58
Math and Science / Re: .9 repeating equals 1?
« on: December 11, 2013, 04:28:33 am »
1) It does not make any sense! It should not equal 1!  :crazy:
Do you have a specific argument against it?

59
Computer Projects and Ideas / Re: haroldbot (theorem prover / solver)
« on: December 04, 2013, 03:29:09 pm »
Progress update:
I've been working on a complete rewrite - and I do mean complete. Everything from the BDD engine to the parser to the IRC interface is completely new and more awesome. The basic idea remains the same, but it should be more efficient, and allow for larger BDDs (no, not 32x32 multiplication) - no one has needed larger ones yet (and yes I do keep an eye on the queries), but whatever.
Some changes that already happened include (but are not limited to)
- using IRC colours for some things ..
- .. such as the biggest (so far) new feature: if the BDD associated with an AST node is not recognized, recurse to the children and stick an operator in between the results. This should do away with the dreaded "solution isn't constant". The colours indicate whether a node was recognized or not.
- very large expansion of the class of functions detected, such as functions with more than 2 inputs.

I will experiment with recursive functions. My idea is to use a new variable to stand in for the result of the recursive call, then fill in the function itself as that variable (which is pretending to be a function argument) using BDD function composition. Then it's 2 calls deep. Then compose two of those together. 4-deep. I'll keep doing that until the function no longer changes (which means it was expanded deeper than any set of arguments could make it go), or until it times out or runs out of space (functions that go too deep or get too complicated). Does anyone see any obvious problems with that?
Apparently that doesn't work. So no recursion, sorry.

60
Miscellaneous / Re: My Little Pony: Friendship is Magic
« on: November 27, 2013, 08:14:18 am »
How would that even happen?

Pages: 1 2 3 [4] 5 6 ... 16