next »

[gimymblert]

no I don't want a new array (I don't have this benefit with a procedural system I'm setting up because there is no primary array in the first place), I want a "displacement vector" that does not pick the same value twice in the target index.

Think about it, I use procedural generation as a "virtual memory" but I don't see the whole memory at the same time, it's potentially infinite. All I have is calculated index and ranges. So given a primary index and a range, I should be able to find another secondary random index without more information, with all the primary index pointing uniquely to a secondary index.

See it like a function, a function is potentially infinite, but I have immediate random access to indexed values by running the function, for example, for a fonction = f(x²), with "x" being the index, I find a corresponding value x² that is associated without knowing all the values of the function. So for "x = 2" I get "4".

The question is there is such a function for randomly sampling unique indexes in a list?

edit
It can be seen like a hash function, a hash function takes an arbitrary input and associate it to an index in a given range. However it's not perfect as multiple input can match a single index. Perfect hashing goes beyond that and match unique input to unique index, but the algorithm I found (minimal perfect hashing) build a hash base iteration over the data.

In my example the index are known in advance there is no arbitrary input, only arbitrary ouput, so uniqueness is guarantee.

edit2:
Going back to the function metaphor, there is a non random function that is close to that I can use as an example. Imagine a function that is essentially "size-index+2", what it does is that it inverse the order then shift it by 2. Now no index map to itself  but uniquely another number, however it lack the random permutation I'm looking for as it is still ordered.

[ProgramGamer]

I have no idea what a displacement vector is. To google and back I hope.

Edit: I knew what it was, I just didn't know how it was named in english.

Edit2: I guess I should also ask about the randomness of your problem. Do you want the same index to always point to the same unrelated value or do you want a different value each time?

[gimymblert]

"I want to the same index to the same unrelated value"

That's the explanation I was looking for lol I couldn't express it that simply

Yeah that's what I'm trying to achieve, so far by helping me rephrasing my problem I have some new idea to explore already!

For example I was wondering if the function should be essentially a "permutation tree" or something like that (that would be initialized with random weight):






If you have play the game you know what I mean, some attack follow the pylon and permute at the connection until the ground, essentially shuffling them, except I must guarantee uniqueness of mapping.

EDIT:
After some thought I'm not sure it would actually work because of the random range that can be inputed.

[ProgramGamer]

The limit with a permutation tree is that you must swap two existing possibilities values, and you don't guarantee that the index will be different than the resulting value since three permutations can essentially negate to equate to a single one.

How about generating an array out of nothing? Does it matter if some values stay related to their index or do you always want different values?

[gimymblert]

Because I will never have access to the whole range at a time, it's for pseudo infinite world, which is also the problem of the tree, it will expend exponentially with pseudo infinite range. And it also have to deal with possibly multiple pseudo infinite range. Also I need access to sub range and be sure that the sub range is coherent with the complete range. However I think the solution is along this line of thought.

For the permutation tree it would a be specific implementation of the knuth algorithm that do guarantee randomness. I use the megaman game as an illustration not as a method.
https://en.wikipedia.org/wiki/Random_permutation

[ProgramGamer]

Ok, so you want a function that takes a range, a seed and an index and returns a value? That could work if the range is undefined but finite. Not sure how big the seed needs to be though, but it needs to be stored somewhere for sure. You could even make it an object since the function and data strongly correlate to each other.

I have no idea what the knuth algo does so I'll go research that for a sec.

[gimymblert]

I linked the relevant page for knuth.

Yes ,I assume that since the data is strongly correlated, such a function should exist. The only arbitrary is the permutation, it's basically shuffling though.

Let's ignore the seed size for now.

[ProgramGamer]

Lol his algo is almost what I described. If we wanted to be efficient the seed could also indicate the size, and then we'd only need to specify an index. The seed would need to specify the size and the possibility of the permutation and from that and the index you could generate a unique non-repeating number, but I don't know how that would work.

[ProgramGamer]

Let's forget the randomness for now. Let's focus on making an algorithm that can generate a value given a range, a size and a permutation ID, because in the end we'll only need to randomize that permutation ID to make it random.

[gimymblert]

Well that's the "parameters" of the function not the "seed":
- range (size) and index
- the "seed" is an arbitrary value and just there to give an arbitrary "shape" to the permutation.

Also I'm looking at cryptography and cipher for inspiration.

The problem is how do you instant permutation without visiting the whole list anyway. Maybe graphing the knuth algorithm and other can help if we "unroll" them?

[ProgramGamer]

it would be a 3d graph if we "unrolled" it.

[gimymblert]

Lol his algo is almost what I described. If we wanted to be efficient the seed could also indicate the size, and then we'd only need to specify an index. The seed would need to specify the size and the possibility of the permutation and from that and the index you could generate a unique non-repeating number, but I don't know how that would work.

Minus the permutation:

Going back to the function metaphor, there is a non random function that is close to that I can use as an example. Imagine a function that is essentially "size-index+2", what it does is that it inverse the order then shift it by 2. Now no index map to itself  but uniquely another number, however it lack the random permutation I'm looking for as it is still ordered.

Take the size and index return value, it cycle every "size" so we can have:
size-index+random


and have a facsimili, we need "permutation" somewhere there lol

Size - index is a kind of permutation though. I wonder if I can expend using a modulo to permute internal fraction of range? and have random shift inside those range?

[ProgramGamer]

The algorythm comes down to what to swap and in which order, and I think we can use regular math from that point forward. I made a graph:



Basically "permutation" needs to indicate which pairs of numbers to swap and in which order from a base array that is assumed to be [1,2, ... ,r] where "r" is range.

For an example, in my graph of range 3, permutation 1 does nothing, 2 swaps [1] and [2], 3 swaps [2] and [3], 4 swaps [1] and [2] and then [2] and [3] imediatelly after, 5 does the same thing except opposite and 6 swaps [1] & [2], [2] & [3] then [1] & [2] again. if we can break down "permutation" to signify which adjacent pairs of values to swap, we can generate the output on the fly and make the function a reality!

[gimymblert]

Notice that some swap are shift that "loop" for example 123 and 231, 312 are shift of each over, how much shift compose the total of permutation? we can then separate shift from unordered and maybe make specifically unordered sequence? (edit: there is exactly n shift in all the possible permutation)

By the way, I had an idea to partition the range into regular bucket and then apply simple random shift and reversing, but then I realize the bucket will still be ordered which change nothing with bigger number, Then I try to see if I could apply different shift base on overlapping bucket and shift. Then I realize it's a frequency problem, basically big partition to number, so there is an increase amount of step as the number got bigger, but then it's only a few step by order of magnitude (something like O(n Log n) not verified).

But I can't prototype a simple wrap around code for arbitrary offset that overfow the range what the fuck brain? I have done it before and that's supposedly trivial!

[gimymblert]

@Programgamer
https://en.wikipedia.org/wiki/Permutation

[gimymblert]

Code:

size = 13
index = 0

;FrequencyDepth(1000000000, depth = 0)

While Not KeyHit(1); Or True

	suffleIndex(size, index)
	
	
	index = index + 1
		
	Delay 100
	
Wend

WaitKey()
;------------------------------------------------------



Function suffleIndex(size, index)
	ratio = index/size
	
	;If ratio > 0 Then index = size - index/ratio

	index = index Mod size 
	
	Print size-index + " " + index + " " + ":" + ratio
	
End Function




Function FrequencyDepth(n, depth = 0)
	Color 000,255,000
	Print n/2
	If n/2 = 0 Then
	Color 255,000,000
		Print depth
	Else
		FrequencyDepth(n/2,depth+1)
	EndIf
	
End Function

The basis for random permutation I need. The main idea is to randomly offset numbers base on "frequency buckets" Ie we offset all number in a bucket, then we divide the bucket and do the same until we are at number level. The idea is that each bucket have a "common fate" so any number in a bucket is shift by the same amount, as bucket are hierarchical we know the number will fall into the same buckets each time. So following a branch path should lead to unique number indexing without doing permutation of all number explicitly. The offset also have a chance to apply a reverse order in the whole current bucket to spice things up. In the end a vector of displacement will be apply to an index until it map to another one randomly

There is a need to verify I can actually build a consistent "partial tree" using random generation in which only part of tree is build consistently to the whole tree (ie each path should always have the random number given an initial seed.

[ProgramGamer]

does anyone know what the name of this type of curve is? it's generated by two points and two lines and is generally used in vector drawing programs such as flash or photoshop.

[oahda]

Bezier?

https://en.m.wikipedia.org/wiki/Bézier_curve

[indie11]

anyone here tried making a folding joint in unity3d? Trying to make one using hinge joint 2d but failing badly, I just can't get them stiff.. I am trying to make something like this

[Dacke]

There are plenty of ways to do interpolation. If you put points in A and B, but also at the point where the straight segments start, then you can try to fit different curves to those points, which will give you an interpolation.

I don't think a Bézier curve is necessarily what you're looking for. If you want straight segments to transition into curved segments the most common approach is probably Spline interpolation:
https://en.wikipedia.org/wiki/Spline_interpolation

It's a mathematical version of pushing elastic rulers against the points. Which is what ship builders and architects used to rely on to draw nice curves. Do note that the straight segments will bulge a bit in the straight sections if you only use four points (or "knots" in spline terminology). You can put in more points to force it to behave the way you want it to.

If you want to do all the math yourself while keeping it really simple, you can try to fit a 2nd degree polynomial instead.