Not a member yet? Why not Sign up today
Create an account  

  • 1 Vote(s) - 5 Average
  • 1
  • 2
  • 3
  • 4
  • 5
 
V2.17 (devtest only)

#31
(2018-04-06, 02:48 AM)vyrus Wrote:
(2018-04-05, 01:45 PM)Gladyon Wrote: All multi-blocks systems uses the same recursive algorithm.
It's a problem when the blocks are in the same 'line', so PAC are the first to be hit, and long laser setup also.

I managed to change it to an iterative algorithm for a part of the fuel exhausts algorithm (the part that is looking for the exit point, it was reaching the stack very fast).
But I failed for the main algorithm. We are trying again with a different approach.

I have no idea what the algorithm looks like, but you could see if it's viable to use tail-end recursion instead. That way you *should* be using only one stack frame, if the compiler optimizes it properly.

Stack, or LIFO, is what I'm thinking too, really.. but I think real problem is probably if the function calls themselves are stacked, instead of just the queue. That is.. essentially:
object.check(objec.check(object.check(object.check(object.check(object.check( ... ))))))
You'll end up with thousands of recursive function calls. Instead you could have an actual stack of object references.

If / when you want to handle a tree, or graph, you'll have splitting paths which makes it more difficult. Mmh... maybe depth-first traversal of the graph, while storing the object pointers into array for LIFO handling. If each object had an iterator for it's children, you could add the returned children into LIFO. If iterator returns the object itself first, and null once it has exhausted the list, without automatic reset.. the iterator itself could act as marker that avoids loops.

Of course the iterator could include conditions regarding the children it returns, like the object can have knowledge of which types of objects it actually sends connection ahead - and likewise the target object can have a boolean function to query whether it accepts the connection. These essentially define the valid connections of the graph.

Code:
// o = initial object on graph
// stack = array to gather all objects
// x = maximum objects gathered from graph
// returns number of items in stack
int makeLifo(object o, object[] stack, int x) {
    int i = 0
    int j = 0
    int[] splits = new int[x]
    while(o && i < x) {
        o = o.getNext()
        if (o) {
            // we can go deeper in tree
            splits[i] = i-1 // initially we just go to previous object for parent
            stack[i++] = o
        } else {
            j = splits[i] // stack[i] had no more children, recall next parent that might have more children
            // now find next path to travel
            while(!o && j >= 0) {
                o = stack[j].getNext() // see if this object has more children
                if(o) {
                    // once we find child, we know that any objects we tested earlier have no more children
                    // this means in future when traversing down, we can skip anything from stack[i] to stack[j+1]
                    splits[i] = j
                } else {
                    j = splits[j]
                }
            } // while(!n && j >= 0)
        } // if(o)
    } // while(o && i < x)
    return i
}

Now you should have all the objects from the graph in the stack. Next you come down the LIFO to handle each of the objects. The problem here is, that the LIFO doesn't really know which objects are connected to others, it only knows the list of all objects.

One possibility would be to build a "handler" function that takes care of the logic. As we travel down the LIFO, we know that each consequent object we call, is "lower" in the graph, in other words children are always processed before their parent.

First, reset iterators - even if something goes wrong later, the objects are prepped for next cycle

Code:
resetIterators(object[] stack, int j)
{
  while (j--) stack[j].resetIterator()
}
Then handle the stack of objects

Code:
handleStack(objecct[] stack, object handler, int j)
{
  handler.stackStart(stack)
  while (j--) handler.stackReport(stack,stack[j])
  handler.stackDone(stack)
}

Now the handler gets reports of objects in the stack, always from children towards their parent. For example for engine, the handler would first get fed all the turbos, and chargers, then a carb. It could gather the numbers, and the next carb would pick them up, at which point the numbers would reset. Carbs in turn would attach to next cylinder, and cylinders to next engine block. This would work as long as the carb doesn't need to know exactly what objects are connected to it. If that's necessary, the handler could be made slightly more complex - collecting an array of connected objects, and then reporting it to their parent.. and likewise it could use that array to tell the children when their parent is found (or the parent itself could do this when handed the array of children).

I haven't actually tried this code, I was just kind of writing it as I was thinking - so it's entirely possible there's some issues with it.
Workshop: Voidware, INARI and more.
Reply

#32
(2018-04-05, 02:08 PM)Kiriko Wrote: Hm.. first approach that comes to mind would be.. giving the components a function that returns the directions and types of connections it sends out, and the "feeler" maintaining a queue of those connections, going through them in iterative loop. Another function perhaps to define the connections it accepts inwards ("Do you accept connection type 2 from west?", return T/F).

So a feeler triggers on specific coordinates, finds component that returns "I send type 2 to N with step 1, and type 3 to E and W with step 2. Feeler would queue 2N1, 3E2 and 3W2, then pick the first in queue to test for component that matches type 2 from 1 position "N" from original. Well the queue would need to have actual coordinates for the test of course.. but anyway. Probably would also need to maintain internal list of blocks that have already been processed to avoid multiple passes on same block.

Feeler could probably be set to process up to N blocks per frame, to spread huge systems across multiple frames - although it would mean initializing the system could take a moment.


(2018-04-06, 02:48 AM)vyrus Wrote: I have no idea what the algorithm looks like, but you could see if it's viable to use tail-end recursion instead. That way you *should* be using only one stack frame, if the compiler optimizes it properly.


The problem is not to find an algorithm which works, that's easy.
The problem is to salvage as much as possible the existing code in order to lose less time and avoid bugs.

The current algorithm is doing a lot of little things which are very important, and there's no real documentation, the only way to re-do completely the algorithm would be to find out everything it is currently doing, or bugs will appear from nowhere...
Reply

#33
(2018-04-06, 08:16 AM)Gladyon Wrote: The problem is not to find an algorithm which works, that's easy.
The problem is to salvage as much as possible the existing code in order to lose less time and avoid bugs.

The current algorithm is doing a lot of little things which are very important, and there's no real documentation, the only way to re-do completely the algorithm would be to find out everything it is currently doing, or bugs will appear from nowhere...

Well that kind of makes sense of course, but if the recursive function calls for each object in the system are what actually causes the problem, wouldn't that mean that the basic structure of the code needs to change ( that is, you can't use a true recursion function to handle the feeler )? Well I should probably look closer to it before saying that. Confused

What I was thinking there, was to simulate a recursion function, through iteration. I guess what I wrote before could make three passes through the stack... first "before sending out feelers", essentially... then the "reporting to handler" and finally "after sending out feelers", or something like that - well... honestly I'm not familiar enough with the feeler recursion to know if it would have a chance of working. What that code -should- be able to do though, is to create an array that has all the objects of the system in an order which recursion would traverse them - but without doing a deep recursion to discover them.

Either way it was nice enough thought exercise. Sleepy
Workshop: Voidware, INARI and more.
Reply

#34
(2018-04-06, 08:25 AM)Kiriko Wrote: Well that kind of makes sense of course, but if the recursive function calls for each object in the system are what actually causes the problem, wouldn't that mean that the basic structure of the code needs to change ( that is, you can't use a true recursion function to handle the feeler )? Well I should probably look closer to it before saying that. Confused

What I was thinking there, was to simulate a recursion function, through iteration. I guess what I wrote before could make three passes through the stack... first "before sending out feelers", essentially... then the "reporting to handler" and finally "after sending out feelers", or something like that - well... honestly I'm not familiar enough with the feeler recursion to know if it would have a chance of working. What that code -should- be able to do though, is to create an array that has all the objects of the system in an order which recursion would traverse them - but without doing a deep recursion to discover them.

Either way it was nice enough thought exercise. Sleepy

It's not a standard recursive algorithm, it's more like a double one (A calls B which calls A, etc.).
I say 'more like', because it's not exactly that, it's more like A calls B, then B, then B, then B, etc. And B calls A.
I say more like, because it's a bit more messy than that...

I'm aware of the standard ways of translating a recursive algorithm into an iterative one using a queue or a stack, the problem is that the ones who thought about these methods never intended to transform such a messy algorithm.
I made the transformation, but something went wrong and nothing was working anymore, and I couldn't fix it easily, so I reverted the changes.

The current code works quite well, there's no bug (except for the stack exception), so we do not want to break it if we can avoid it.


Nothing can be taken for granted in a large software, and FtD is a large software, so nothing is as simple as it should, unfortunately...

But you're right, just for the sake of the exercise it's a good thing to think about ways of transforming a recursive algorithm into an iterative one.
But if you want an advice, when you code, never use a recursive algorithm if there are chances that it will go over 100 recursions.
If you're sure it will be less than 100 then it's perfectly fine, because it's more readable.
But if you don't control the number of recursions (in this case, Nick do not control the number of blocks you want to place in a PAC arm), then it's a bad idea, because sooner or later it will fail.
Reply

#35
If it's just a stack issue, surely changing it's basics so you have your own stack of references to previous objects & repeatedly calling whatever function it is with the current stack head is going to sort that - it's the same functionality without all the stack overhead of shoving the entire function call on there. What is the actual issue with removing recursion?
Poke my boat! mostly pre-2.0 learning & catalogue thread - Update: Heavy & light tanks 07/04/18 for 2.1. 6 ships made 2.0 aware. No more post-processing! finally! but now I can't read the forum.
Reply

#36
(2018-04-06, 12:06 PM)Richard Dastardly Wrote: If it's just a stack issue, surely changing it's basics so you have your own stack of references to previous objects & repeatedly calling whatever function it is with the current stack head is going to sort that - it's the same functionality without all the stack overhead of shoving the entire function call on there. What is the actual issue with removing recursion?

You have to store each function context also.
And as there are a lot of different functions calling each other it is a lot more complex than just having one structure (the context) that we put on a stack.
We would need several structures, one for each function that can be called, and each containing a pointer to the function to call.

Also, in a standard recursion you call the next 'layer' at the end of the recursive function, here, the next 'layer' is called several times in one of the recursive function (I say one, because it do not call itself, there are some other in-between).
So, putting the calls on a stack until the function is finished, and then unstacking the first one would change the order of the calls.

I may be wrong and I may see complexity where it is not, but I doubt it.
I tried to create a stack and to place some sort of context on it, but I have been unable to reproduce exactly the order of the calls of the multiple layers and in the end the algorithm's result was completely different.


As I said, nothing is that simple in FtD...
And anyway, Nick said he'll try, and as he knows exactly what the current algorithm does, how it does it, and why it does it like that, he may have more luck than me.
Reply

#37
Sounds like something that really should be addressed at some point here, especially since it seems like a similar functionality that's being called for multiple multi-block systems. Maybe when you get Nick's help on stuff you can get him to pitch in on an effort to rewrite it. Undecided
Reply

#38
Im glad you guys know this stuff cuz its way over my head. FTD to lucky to have you.
Reply

#39
I'm noticing texture changes. Nice job if intentional (duh) but there are holes in the fuel engine exhaust corners. Just saying.
There are two rules of thumb in this world:
- These warheads are great! Explosive are my favourite! Nothing beats an explosive warhead.
- If explosives aren't enough, spam more explosive. At some point they will break open.
Reply

#40
The new textures / shaders are intended, but not definitive.
I don't have a lot of detail about them, as I only work with the code.
Reply



Forum Jump:


Users browsing this thread:
1 Guest(s)