Move Tree

OGS Development
1

I am building a prototype of a SGF viewer and was wondering if someone could breakdown the Move Tree class.
I dont need really need the Goban, or GobanCanvas or GobanEngine in this case as I want to build all functionality into the graph itself.

Right now using D3js I can come close but creating dummy nodes to fix the align doesnt seem to be working either.

I am using SabakiHQ/sgf to get the game tree
Then I am recursively going through the tree to create links and add x and y coordinates. After this I go through a hashmap of the moves and set the Y value to move[index] * stone_size.

Which feels correct except you can see that not all variations are straight.

image

2

没太明白，是对画的图不太满意，不希望分支向上拐吗？如果是那样递归的时候记录一下行数就行了吧。毕竟没放代码，别人也帮不了啥吧。

3

I posted this half asleep, didn’t realize I didnt post the code…

    // const width = 1280;
    // const height = 720;
    // const Ylevel = 50;
    // const Xdist = 50;
    const stoneRadius = 20;
    const dom = new JSDOM('<!DOCTYPE html><body></body>');
    global.window = dom.window;
    global.document = dom.window.document;
    
    function calculateTreeDimensions(root) {
        let queue = [root], depth = 0, maxWidth = 0;
    
        while (queue.length) {
            maxWidth = Math.max(maxWidth, queue.length);
    
            let nextLevelNodes = [];
            for (let node of queue) {
                if (node.children) {
                    nextLevelNodes.push(...node.children);
                }
            }
            queue = nextLevelNodes;
            depth++;
        }
    
        return { width: maxWidth, height: depth };
    }
    
    const dimensions = calculateTreeDimensions(sgfData);
    
    let flattenedNodes = [], links = [], moveNumbers = {};
    for (let move = 0; move < dimensions.height; move++) {
        moveNumbers[move] = Array(dimensions.width).fill().map(() => ({ id: "dummy" }));
    }
    
    let depthIndexCounters = {};
    
    function recursiveLinks(node, yOffset = 0, move = 0) {
        node.move = move;
        node.color = node.data.B ? "black" : "white";
    
        depthIndexCounters[move] = (depthIndexCounters[move] || 0) + 1;
        moveNumbers[move][depthIndexCounters[move] - 1] = node;
    
        flattenedNodes.push(node);
        node.x = node.move * 50 + 25;
        node.y = 50;
    
        (node.children || []).forEach((child, index) => {
            links.push({ source: node.id, target: child.id });
            recursiveLinks(child, yOffset + index, move + 1);
        });
    }
    
    recursiveLinks(sgfData);
    Object.values(moveNumbers).forEach(nodes => {
        nodes.forEach((node, index) => node.y += index * 50);
    });
4

yOffset, I guess, should be the number of leaf nodes that have been visited in DFS.

    let links = [];

    function recursiveLinks(node, yOffset = 0, move = 0) {
        node.move = move;
        node.color = node.data.B ? "black" : "white";
    
        node.x = node.move * 50 + 25;
        node.y = yOffset * 50 + 50;
    
        (node.children || []).forEach((child, index) => {
            links.push({ source: node.id, target: child.id });
            yOffset = recursiveLinks(child, yOffset, move + 1);
        });

		if(!node.children){
			++yOffset;
		}

        return yOffset;
    }
    
    recursiveLinks(sgfData);

I didn’t test it as you didn’t post any data.

2 Likes
5

If you want it to be more compact

    let links = [];
    let depthIndexCounters = {};
    
    function recursiveLinks(node, yOffset = 0, move = 0) {
        node.move = move;
        node.color = node.data.B ? "black" : "white";
    
        depthIndexCounters[move] = (depthIndexCounters[move] || 0) + 1;
        yOffset = Math.max(yOffset, depthIndexCounters[move]);
    
        node.x = node.move * 50 + 25;
        node.y = yOffset * 50;
    
        (node.children || []).forEach((child, index) => {
            links.push({ source: node.id, target: child.id });
            recursiveLinks(child, yOffset, move + 1);
        });
    }
    
    recursiveLinks(sgfData);
6

Thanks! It worked pretty well!

image
image748×505 19.7 KB

I had to modify it a little bit, since I am using JavaScript

    function recursiveLinks(node, yOffset = 0, move = 0) {
        node.move = move;
        node.color = node.data.B ? "black" : "white";

        depthIndexCounters[move] = (depthIndexCounters[move] || 0) + 1;
        yOffset = Math.max(yOffset, depthIndexCounters[move]);

        node.x = node.move * 50 + 25;
        node.y = yOffset * 50;

        flattenedNodes.push(node);
        
        if (node.children) {
            node.children.forEach((child, index) => {
                links.push({ source: node.id, target: child.id });
                recursiveLinks(child, yOffset, move + 1);
            });
        }


    }

Appreciate the help!

1 Like
7

Oh, sorry. This structure will trigger a bug.
test
Edit:

    function recursiveLinks(node, yOffset = 0, move = 0) {
        node.move = move;
        node.color = node.data.B ? "black" : "white";

        yOffset = Math.max(yOffset, (depthIndexCounters[move] || 0) + 1);
        depthIndexCounters[move] = yOffset;

        node.x = node.move * 50 + 25;
        node.y = yOffset * 50;

        flattenedNodes.push(node);
        
        if (node.children) {
            node.children.forEach((child, index) => {
                links.push({ source: node.id, target: child.id });
                recursiveLinks(child, yOffset, move + 1);
            });
        }
    }

Maybe this looks better.

    function recursiveLinks(node, yOffset = 0, move = 0) {
        node.move = move;
        node.color = node.data.B ? "black" : "white";

        yOffset = Math.max(yOffset, (depthIndexCounters[move] || 0) + 1, (depthIndexCounters[move + 1] || 0));
        depthIndexCounters[move] = yOffset;

        node.x = node.move * 50 + 25;
        node.y = yOffset * 50;

        flattenedNodes.push(node);
        
        if (node.children) {
            node.children.forEach((child, index) => {
                links.push({ source: node.id, target: child.id });
                recursiveLinks(child, yOffset, move + 1);
            });
        }
    }
1 Like
8

The second one worked best. Would you mind explaining to me how the change works?
Why does setting the yOffset work like so?

image
image840×426 21.8 KB

I’m not exactly sure how this specific recursive function is displaying the nodes like so but.
I imagine this is keeping track of every new value at move in the hashmap and when a move in the same column is played its adding a depth?
Is this interpretation correct?

9

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.