Forem: Aleksandr Churbakov

How is Braid made?

Aleksandr Churbakov — Sat, 06 Jul 2024 10:19:38 +0000

There is an indie game called Braid, a very popular one. The core feature of the game was time rewind mechanic - you could've just stopped time and ran it backwards. I, software developer, was very curious about how to make such a game and tried it myself. Here's what I learned.

A little bit of information for those who missed the game. Braid is an indie-game from Jonathan Blow made in 2008. It became a bestseller, sold more than 55 thousand times during first week after release.

Game Trailer

All the GIFs are interactive examples on my webpage, the link will be shown in the end of the article

Start from scratch

Let's simplify - imagine that we make a game about moving a dot in one dimensional space. Using W and S we move the dot along vertical axis and right to it we show a timeline with dot position from time. Also we display all key pressed on the timeline.

Usually moving an object in a game is made with special timer, every tick of which changes object position so slightly, just a few pixels. It happens about 30 times a second and creates an illusion of smooth transition. That's an imperative approach.

const STEP_PER_TICK = 2; // 2 pixels per 1/30 of a second
const dotPosition = DEFAULT_POSITION;

movement.on('tick', () => {
    if (keys[UP]) {
        dotPosition += STEP_PER_TICK:
    }

    if (keys[DOWN]) {
        dotPosition -= STEP_PER_TICK:
    }
});

render.on('tick', () => {
    drawCircle(dotPosition, 'black');
});

But sometimes applications utilize another approach - a declarative one. Instead of changing position and updating a variable, we can simply describe how ball position depends on the time - dotPosition(t), where t is current time.

But how? Well, we can use events timeline. For example, if the last event is W keypress, we can simply take dot position at event time and add speed * time difference.

const getDotPosition = (t) => {
    const { position, type, time } = getLastEvent(events, t);

    const speed = {
        RELEASE: 0,
        UP: -1,
        DOWN: 1,
    }[type];

    return position + speed * (t - time);
};

render.on('tick', () => {
    drawCircle(getDotPosition(now()));
});

Now we don't need to store dot position at all - every time we need to render the dot, we can calculate dot position from current time. Note that now dot position can have decimals since time difference between renders may not be stable and does not equal to 1/30 of a second. Moreover, pressing W and S at the same time does not cancel movement.

Reverse time

Now we can add another term - inner time. The thing is that instead of current time (that we get by calling now()) we can pass in something else. For example, if we just pass now() / 2 we can slow the time down.

render.on('tick', () => {
    const time = now() / 2; // time is twice slower

    drawCircle(getDotPosition(time));
});

But that's not exactly what we wanted. We want to control the time§ with keyboard. Not only slow down or speed up, but to rewind. We want the inner time to depend on outer time somewhat like this:

Looks familiar, right? Yes, that exactly the timeline we saw for dot position! Inner time depends outer time the same way, that dot position depends on inner time Just instead of W and S we use Space to control that timeline.

const timeEvents = []; // space press events
const gameEvents = []; // W and S press events

const getInnerTime = (t) => {
    const { value, backward, time } = getLastEvent(timeEvents, t);
    const change = backward ? -0.8 : 1;

    return value + change * (t - time)
};

const getDotPosition = (t) => {
    const { position, type, time } = getLastEvent(gameEvents, t);

    if (type === RELEASE) {
        return position;
    }

    const change = speed * (t - time);

    return position + change * (type === UP ? 1 : -1);
};

render.on('tick', () => {
    const innerTime = getInnerTime(now());
    const dotPosition = getDotPosition(innerTime);

    drawCircle(dotPosition);
});

What we end up having is waterfall of functions. First we take outer time (system time) and calculate inner time (the one you can see in the top of timeline). Only then we take that inner time and calculate dot position. Both times we use events log (W, S and Space presses) to figure out how to calculate value. Isn't that awesome?

Second dimension

Let's go further and add second dimension. Now the dot will move not only along vertical axis, but along horizontal too. Also we'll update the timeline to display position in 2d and use depth for time.

const add = (a, b) => ({ x: a.x + b.x, y: a.y + b.y });
const mul = (a, b) => ({ x: a.x * b, y: a.y * b });

const getDotPosition = (t) => {
    const { position, directions, time } = getLastEvent(gameEvents, t);

    // now position is Point { x, y }

    const change = speed * (t - time);

    const direction = sum(...directions.map((dir) => ({
        return {
            up: { x: 0, y: -1 },
            down: { x: 0, y: 1 },
            left: { x: -1, y: 0 },
            right: { x: 1, y: 0 },
        }[dir];
    }));

    return add(position, mul(direction, change));
};

render.on('tick', () => {
    const innerTime = getInnerTime(now());
    const dotPosition = getDotPosition(innerTime);

    drawCircle(dotPosition);
});

Add acceleration

Important thing that we still miss is acceleration. A lot of the times platformer's objects actually don't move in a linear fashion, but rather with acceleration. When they fall, for example. Imperatively this would've been done somewhat like that:

let gravity = 10;
let speed = 0;
let position = 100;

// ...

movement.on('tick', () => {
    speed += gravity;
    position += speed;
});

render.on('tick', () => {
    drawObject(position);
});

But we don't have variables for position or speed - we have to define functions to figure out dot position of time. To mind acceleration we should recall school math, specifically uniform acceleration.

Uniform Acceleration

const getBallPosition = (t) => {
    const event = getLastEvent(gameEvents, t);

    if (event.type === 'fall') { 
        return {
            // x doesnt change
            x: event.position.x, 
            // formula from wikipedia
            y: event.position.y
                + event.velocity * (t - event.time)
                + .5 * GRAVITY * ((t - event.time) ** 2)
        };
    }
};

As you can see event how should not only store position, but velocity too. So we need to calculate that for a given time as well. In the end I got something like this:

class GameDot extends Timeline {
    getDirections = (innerTime: number) => {
        const event = this.get(innerTime); // last event for given time

        return event.data.directions;
    };

    getAcceleration = (innerTime: number) => {
        return sum(
            { x: 0, y: 0 },
            ...this.getDirections(innerTime).map((dir) => ({
                up: { x: 0, y: -ACC },
                down: { x: 0, y: ACC },
                left: { x: -ACC, y: 0 },
                right: { x: ACC, y: 0 },
            }[dir] || { x: 0, y: 0 })),
        );
    };

    getVelocity = (innerTime: number) => {
        const event = this.get(innerTime);
        const acceleration = this.getAcceleration(innerTime);

        return add(
            event.data.velocity, 
            mul(acceleration, (innerTime - event.time))
        );
    };

    getPosition = (innerTime: number) => {
        const event = this.get(innerTime);

        const acceleration = this.getAcceleration(innerTime);

        return sum(
            event.data.position, 
            mul(event.data.velocity, innerTime - event.time),
            mul(acceleration, .5 * ((innerTime - event.time) ** 2))
        );
    };
};

Finally combine together

Now we have to combine all of that together! Left and right movement will be linear, jump and fall will be uniformely accelerated. Also I will add a special event of touching the ground (platform).

I won't add all of the code here, because I didn't have a goal to make it into real game, but rather to replicate game mechanic. Here's what it looks like in the end:

That's it! Of course tons of stuff is not covered - mobs, death or stairs. But I wanted to talk about rewind specifically. Please let me know if you like this article as I am only considering gamedev articles (that's my first one). Thank you!

Interactive article in author's blog

My React Hooks

Aleksandr Churbakov — Fri, 22 Sep 2023 12:01:53 +0000

React is dominating Frontend development and no wonder more than a half of applications being written are using it. The simplicity and strength is powered by tons of great features and React Hooks is one of them. As a Frontend developer I've been writing and using hooks almost every day of my career for the last couple of years. A lot of the hooks I've used were quite universal so I've spotted them migrating from one of my project to another without almost any change.

I'm not the only developer who has noticed that and you can easily find tons of React Hooks on npm, but introducing an additional dependency for a thing that takes less than 30 lines of code is a bit of a controversial decision, so over time I naturally have been choosing to write them myself. My collection grew and became quite big and useful, so here I am to share.

I'm still not making a library of it and treat the following code more as of a snippet rather than a package, cherry pick hooks I need and copy them to my project. That way I avoid useless complexity of either importing extra 3 to 5 libraries or maintaining a full size npm package while having a flexibility to edit the hooks the way my project may require - those are 10-20 liners in the end of day.

useLocalStorage

export const useLocalStorage = <T,>(key: string, def: T) => {
    const [value, setValue] = React.useState(JSON.parse(localStorage.getItem(key) || JSON.stringify(def)) as T);

    React.useEffect(() => localStorage.setItem(key, JSON.stringify(value)), [value]);

    return [value, setValue] as const;
};

Pretty straightforward and simple hooks that you can find almost everywhere. You can change it to be somewhat durable by providing a "safer" version of JSON.parse or switch to session storage (or even cookies using universal-cookies get and set method).

useQueryParam(s)

export const useQueryParam = <T>(name: string) => {
    const params = new URLSearchParams(window.location.search);
    const value: T = params.get(name) || null;

    const setValue = (v) => {
        const params = new URLSearchParams(window.location.search);

        if (v) {
            params.set(name, v);
        } else {
            params.delete(name);
        }

        window.location.search = params.toString();
    };

    return [value, setValue] as const;
};

Another simple one, usually I keep it being split in 2 hooks: useQueryParams (meaning all the params) and useQueryParam(name), but here I list a compiled version.

useEventListener

export const useListener = (target: any, event: string, callback: EventListenerOrEventListenerObject, deps: React.DependencyList) => {
    React.useEffect(() => {
        target.addEventListener(event, callback);
        return () => target.removeEventListener(event, callback);
    }, [...deps, callback]);
};

This one is easy too, you can update this hook to include options that you can pass to addEventListener method. Usually I use this one to add listener to window. Don't forget to wrap callback into React.useCallback!

useForceUpdate

export const useForceUpdate = ([_, setState] = React.useState(false)) => 
    React.useCallback(() => setState(s => !s), [setState]);

The smallest, but quite an important one. Usually I wrap this into const ticker = useTicker() hook and force container update on POST/PUT/DELETE actions (will explain in details later).

useClickOutside

const useClickOutside = (predicate) => {
    const ref = React.useRef(null);

    useListener(window, 'click', (e) => {
        if (!ref.current.contains(e.target)) {
            predicate();
        }
    }, [predicate]);

    return ref;
};

That one returns a ref that, being attached to an element, will cause any click outside of this element to call predicate.

<Modal ref={useClickOutside(onClose)}>{...}</Modal>

useDebouncedEffect

Imagine you need to save user's Figma file when it's updated, but you don't want to do this every time something changes. You probably want to debounce update calls:

const useDebouncedEffect = (predicate, time, deps) => {
    const timeoutRef = React.useRef(null);

    React.useEffect(() => {
        if (timeoutRef.current) {
            clearTimeout(timeoutRef.current);
        }

        timeoutRef.current = setTimeout(predicate, time);
    }, deps);
};

This one will only call your effect once in a time. Please note that predicate is not a part of deps and you probably want to change that, but, if you do, remember to wrap it with React.useCallback!

useDebouncedEffect(() => api.patchProfile({ name }), 500, [name]);

return (<TextInput value={name} onChange={setName} />);

useRefCallback

Sometimes you want to do something with a delay and use setTimeout like I did in example above or perform an async call and call some function after. Sometimes that can cause bugs because inside timeout/promise handler you might be calling an "old version" of whatever function you wanted to call. These kinds of bugs are quite tricky to catch, but if you've found one, you can use the following hook:

const useRefCallback = (callback) => {
  const ref = React.useRef(null);

  React.useEffect(() => {
    ref.current = callback;
  }, [callback]);

  return ref;
}

Using this instead (together is fine too actually) of useCallback you can get a fresh version of your callback any time you call it. But you will have to access it with .current.

usePreviousValue

Following up the hook above comes the previous value container.

const usePreviousValue = (value) => {
    const ref = React.useRef(value);
    const pref = React.useRef(value);

    React.useEffect(() => {
        pref.current = ref.current;
        ref.current = value;
    }, [value])

    return pref.current; // SIC!
};

This hook will return the previous value of (you guessed it) value. I actually like to return ref instead of a value itself to highlight the nature of previous value and remove an incentive to hook an effect to it. This isn't forbidden, but it's better not to do so and listen to original value instead.

useInput & useValidate

Sometimes you may find yourself in a position of making a form for a simple input or two and not willing to bring in formik artillery or whatever form library you are into.

const useInput = <T,>(def: T) => {
    const [state, setState] = React.useState(def);

    return { value: state, onChange: setState } as Input<T>;
};

const useValidate = <T,>(input: Input<T>, ...validators: Validator<T>[]) => {
    const [error, setError] = React.useState(null);

    React.useEffect(() => {
        for (let validator of validators) {
            const error = validator(input.value);

            if (error) {
                setError(error);
                return;
            }
        }

        setError(null);
    }, [input.value]);

    return error;
};

Those 2 usually go together and let me easily create simple forms like this:

const require = ($) => !$ && 'Required field';
const min = (n) => ($) => $.length < n && `Should have at least ${n} characters`;

const name = useInput('');

return (
  <Input {...name} error={useValidate(name, required, min(5))} />
);

useAsyncMemo

Quite a popular one, you may have seen that as react-query used with GraphQL a lot. This is the essence of it:

export const useAsyncMemo = <T,>(predicate: Predicate<[], Promise<T>>, deps: React.DependencyList) => {
    const [loading, setLoading] = React.useState(false);
    const [value, setValue] = React.useState(null as T | null);
    const [error, setError] = React.useState(null as Error | null);

    React.useEffect(() => {
        setLoading(true);

        predicate().then((value) => {
            setValue(value);
        }).catch((error) => {
            setError(error);
        }).then(() => {
            setLoading(false);
        });
    }, deps);

    return [value, loading, error] as const;
};

Please again note that deps don't include callback, but if you add it here, wrap it with useCallback.

useObservable

If you happen to use rxjs with your React project (and they get along really well), you can use the following code as a replacement for async pipe:

export const useObservable = (o) => {
    const [value, setValue] = React.useState(null);

    React.useEffect(() => {
      let sub = o.subscribe((value) => setValue(value);
      return () => sub.unsubscribe();
    }), [r]);

    return value;
};

useWorker

Very simple and effective hook to delegate computation heavy tasks to a separate process.

const useWorker = (handler, callback) => {
  const workerRef = React.useRef(null);

  React.useEffect(() => {
    const worker = new Worker(URL.createObjectURL(
      new Blob([
        `onmessage=${handler}`
      ], { type: 'text/javascript' })
    ));

    worker.onmessage=callback;
    workerRef.current = worker;

    return () => worker.terminate();
  }, [handler, callback]);

  return workerRef;
};

useBetween & useTicker

Finally, my favorite one. It's a separate npm library written by a great guy @betula that you can find here https://github.com/betula/use-between. It's a great replacement for all the useContext mess on my pet projects.

const useTicker = ([state, setState] = React.useState(false)) => React.useMemo(() => ({ update: () => setState($ => !$) }, [setState, state]);

const _useAuth = () => {
  const ticker = useTicker();
  const token = useLocalStorage('token', null);
  const [user] = useAsyncMemo(() => api.session.get(token), [token, ticker]);

  const updateName = React.useCallback((name) => {
    api.session.patch(token, { name })
      .then(ticker.update)
      .catch(/* notify */);
  }, [token]);

  return { user, updateName };
};

const useAuth = () => useBetween(_useAuth);

That's how I've been designing my shared state and methods ever since I've found this great library. Any React Component using useAuth hook will receive the same data and it will be up to date as soon as you update user name.

And it's all I wanted to share. Feel free to post any cool React Hooks you know in the comments below.

How to make a logic circuit with Conway's Game of Life

Aleksandr Churbakov — Thu, 24 Nov 2022 10:05:31 +0000

Most likely you already heard about Conway's Game of Life and you know that it's, in fact, Turing-Complete, meaning that you can make a full size computer with it.

Let's take a deeper look on how to make a simple circuit.

Getting Started

First of all we will need a way to run game of life. I am a JS dev so I've made a website with game of life simulation using one of my old projects, you can check it in this snapshot.

One thing to notice is that we make a parse function to load RLE which is JSON for game of life state. The very first RLE example you can see is 24bo$22bobo$12b2o6b2o12b2o$11bo3bo4b2o12b2o$2o8bo5bo3b2o$2o8bo3bob2o4bobo$10bo5bo7bo$11bo3bo$12b2o! which is Gosper Glider Gun. We'll use this RLE to test application and parsing function, which should look like following:

const isDigit = (s: string) => 
    '0123456789'.indexOf(s) > -1;

const splitIntoTokens = (rle: string) => {
    let buffer = 1;

    return rle.split('').reduce((acc, token) => {
        if (isDigit(token) && acc.length > 0 && isDigit(acc[acc.length - 1])) {
            acc[acc.length-1] += token;
            return acc;
        } else {
            return acc.concat([token]);
        }
    }, []).reduce((acc, token) => {
        if (token === '$') {
            return acc.concat([{ type: '$' }]);
        } else if (token === '!') {
            return acc.concat([{ type: '!' }]);
        } else if (token === 'b') {
            const count = buffer;
            buffer = 1;
            return acc.concat([{ count, type: 'b' }]);
        } else if (token === 'o') {
            const count = buffer;
            buffer = 1;
            return acc.concat([{ count, type: 'o' }]);
        } else {
            buffer = parseInt(token, 10) || 1;
            return acc;
        }
    }, []);
};

export const parse = (rle: string) => {
    let y = 0;
    let x = 0;

    return splitIntoTokens(rle).reduce((acc, token) => {
        if (token.type === '$') {
            y++;
            x=0;
        }

        if (token.type === 'b') {
            x += token.count;
        }

        if (token.type === 'o') {
            for (let i = 0; i < token.count; ++i) {
                acc.push({ x: x + i, y });
            }
            x += token.count;
        }

        return acc;
    }, []);
};

After little bugfixing we should see the game itself in the browser. I am not adding game simulation code here as it's pretty straightforward and easily googlable.

The Circuitry

Before we design something meaningful, we have to understand what our building bricks are. The whole Game of Life's circuitry is built around few simple components.

Glider Gun

There are few different types of glider guns, they vary by period, glider direction and perks like ability to be destroyed or modified to change glider output. We'll stick to Gosper Glider Gun as the smallest (box wise).

Gosper Glider Gun produces a glider in a specific direction every 30 generations, building a so-called "stream" of gliders.

Glider

Glider is a basic but very usable Game of Life pattern. In circuitry it is used to transfer bit signal. Gliders cannot cary any information within them, but their presence inside the "stream" at a specific point of time (generation) can be interpreted as 1 or 0, somewhat like baud rate.

One important thing to know about Gliders is that, if they collide in just the right way, they annihilate each other.

Glider Reflector

Reflector is Game of Life pattern that will allow us to "redirect" the glider stream in a different direction. Again, there are few different types of reflector that work with different "baud", different angle or have interesting abilities to mutate, in this article we'll use this one.

Glider Eater

Glider Eater is a pattern that, being shot with a glider in just the right way, will destroy a glider. This is usable to end the "glider stream" if don't want it to mess with the rest of the circuit.

Drawing Patterns

Now we have all the knowledge to play around and try to make our own gates, but we don't have a way to do it. Let's modify the application we've made to support simple drawing around and pausing. This way we'll be able to create our own patterns and see them in action.

const handlePoint = (x: number, y: number) => {
    if (this.gameOfLife.has(x, y)) {
        this.gameOfLife.remove(x, y);
    } else {
        this.gameOfLife.put(x, y);
    }
};

let mousepressed = false;

this.events.onMouseDown.subscribe(({ x, y }) => {
    mousepressed = true;

    const cellX = Math.floor(x / CELL_SIZE);
    const cellY = Math.floor(y / CELL_SIZE);

    handlePoint(cellX, cellY);
});

this.events.onMouseUp.subscribe(() => {
    mousepressed = false;
});

this.events.onMouseMove.subscribe(({ x, y }) => {
    if (mousepressed) {
        const cellX = Math.floor(x / CELL_SIZE);
        const cellY = Math.floor(y / CELL_SIZE);

        handlePoint(cellX, cellY);
    }
});

You can see how drawing works in this snapshot. After playing around I was able to draw components on my own and made the Glider Reflector pattern, but it took me too much time.

A lot of circuitry for Game Of Life is happening around adjusting distance to make the stream just the right length for gliders to hit reflectors or each other at the right time. In order to achieve this we'll have to move guns and reflectors by a couple of cells here and there. Redrawing Gosper Gun 2 cells left - that's gonna hurt. Let's upgrade our application to support selection and moving.

let selection = null as null | { from: Point, to: Point };

this.events.onMouseDown.subscribe((p) => {
  if (this.modes.get() === 'select') {
    const cell = this.getCellByPoint(p);

    selection = { from: cell, to: cell };
  }                  
});

this.events.onMouseMove.subscribe((p) => {
  if (this.modes.get() === 'select') {
    const cell = this.getCellByPoint(p);

   selection.to = cell;
  }
});

this.navigator.onRender.subscribe((context) => {
  if (selection) {
    const { from, to } = selection;

    context.beginPath();
    context.rect(
      from.x * CELL_SIZE,
      from.y * CELL_SIZE,
      (to.x - from.x) * CELL_SIZE,
      (to.y - from.y) * CELL_SIZE
    );

    context.setLineDash([15, 5]);
    context.lineWidth = 5;
    context.stroke();
    context.setLineDash([]);
  }
});

After that we should be able to select regions of the field. With that selection we can do many different operations like mirroring, rotating and even inverting.

Here is the listing for moving the selection with its content by arrows on the keyboard.

this.events.onKeyDown.subscribe((key) => {
  if (this.modes.get() !== 'select') {
    return;
  }

  // Move with arrows
  if (key === 37) { // left
    this.moveSelection(-1, 0);
  }

  if (key === 39) { // right
    this.moveSelection(1, 0);
  }

  if (key === 40) { // down
    this.moveSelection(0, 1);
  }

  if (key === 38) { // up
    this.moveSelection(0, -1);
  }
}

const moveSelection = (dx: number, dy: number) => {
  this.gameOfLife.state.forEach((cell) => {
    if (this.cellInSelection(cell)) {
      cell.x += dx;
      cell.y += dy;
    }
  });

  this.selection.from.x += dx;
  this.selection.from.y += dy;
  this.selection.to.x += dx;
  this.selection.to.y += dy;
};

Glider Stream

Before we design the gates themselves we should understand the concept of Glider Streams. The Glider Stream is a path that Gliders travel. Usually it starts in a glider gun, goes through several mutations like reflectors and annihilators and ends with a glider eater.

Let's add the highlight for the streams and observe the simplest glider stream. It starts with Gosper Glider Gun and ends with Glider Eater. Every 30 generations new Glider is created and it takes 60 generations for it to reach the glider eater.

If we assume that 30 generations is somewhat a "global period" we can check the presence of glider in the stream every "global period" generations in blue square and, if glider is present, take it as 1, if glider is absent, take it as 0. Thus said, the stream below is a constant stream of 1's.

On the screenshot below you can check 2 glider streams, one of them has a period of 30 and another one has a period of 60, but, if we measure them in one spot with a period of 30, we will see that the bottom stream is a constant stream of 1's, while the top stream's content is 1, 0, 1, 0...

Designing Gates

First of all we will make NOT gate. This gate will take the input stream of gliders (the one coming from the right top) and inverse it.

It'll do so by using a specific trait of gliders - if they collide in just the right time, they annihilate each other. If we collide the input stream with a constant stream, for every glider in an input stream there will be a corresponding emptiness inside the constant stream output (since input stream glider and constant stream glider annihilate each other). But for every empty spot inside the input stream, there will be a glider coming from constant stream as there will be nothing to annihilate it with.

If we add one more stream and make it point towards the constant stream the way it can annihilate gliders, we'll get AND gate. If glider is present in input A stream, it will annihilate the glider in constant stream and let input B go through unaffected.

If glider is not present in input A stream, it will not block the constant stream and input B, whatever it is, will not go through it.

The function we've described (if a is 1 then b else 0) is equivalent to a && b or AND gate.

One thing to notice is that input A and B actually should have an offset to each other. The glider in input B that corresponds to glider in input A comes 60 generations later.

If we add one more stream we'll get a complicated picture. I pointed out all the streams and all the collision places, so you can have a better understanding.

One of the "side effects" of AND gate is a constant stream, after all the collisions it implements not (A or B) expression, which, if being modified with NOT gate, results in not (not (A or B)) or A or B, which is OR gate.

If we get back to just one collision between 2 streams, we'll get a boolean inhibition function.

Now you should be good to make any logic circuit using these gates, feel free to play around inside the repo I've made and comment.

Create a Torrent Application with Node from scratch.

Aleksandr Churbakov — Tue, 12 Apr 2022 09:41:30 +0000

The best way to learn stuff in development is go and try to create your own whatever it is. In this article I'll walk you through creating a minimal example of Torrent application using Node JS and swenssonp2p library.

It is strongly advised to read and comment my previous article about making p2p library from scratch in order to understand this one.

So, Torrent is a P2P network, that lets peers exchange files. The main idea behind it is that one file may appear at different peers and, by chunking and splitting download streams, peers can speed up files download. P2P network is used to exchange meta information about files, while the actual download uses a separate TCP connection directly to the seed.

In this article I won't implement leeches, but you may find this code in the repo later.

Okay, so first of all, I need to come up with some sort of interface for the end user to share the files using this application. I've decided to just index everything inside process.cwd() on application startup.

To store the files I decided to use Map where file's hash will be the key. I also decided that I don't want this process to block user from doing what they want to do and I put indexing inside async function that is not being awaited for. hashFile implementation is up to you.

const path = require('path');
const { readdir, stat } = require('fs/promises');

const index = new Map();

async function* findFiles (folder) {
  for (let filename of await readdir(folder)) {
    const filepath = path.resolve(folder, filename);
    const filestats = await stat(filepath);

    if (filestats.isDirectory()) {
      yield* findFiles(filepath);
    } else {
      yield { path: filepath, size: filestats.size };
    }
  }
}

;(async () => {
  console.log('Start indexing files...');

  for await (let { path, size } of findFiles(process.cwd())) {
    const [name] = path.split('/').slice(-1);
    const hash = await hashFile(path);

    index.set(hash, { hash, size, name, path });
  }

  console.log(`Directory content indexed, ${index.size} files found`);
})();

The next thing I want to do is to create a P2P network. I use swenssonp2p and just call createNode. It will set up a generic p2p network node locally, after that I run listen to start accepting connections.

I don't know exactly what I'll be doing after the startup, I guess there should be many things, so I leave an event emitter call (socket), that I can fill with the listeners later. In order to be able to subscribe before listen callback is called, I delay the listen call until all the synchronous code is completed.

const EventEmitter = require('events');
const createNode = require('swenssonp2p');

const main = new EventEmitter();

const node = createNode();
const port = Number(process.argv[2]);

setTimeout(() => {
  node.listen(port, () => main.emit('startup', port));
}, 0);

After the node is up I proceed and let user know what they can do. I want to use the same interface (typing commands into process.stdin) that I've used in chat application, but I don't know exactly what commands I should have, so I leave a socket (actually two) there as well.

main.on('startup', (port) => {
  console.log(`Node is up on ${port}.`);
  console.log('');

  main.emit('help');

  process.stdin.on('data', (data) => main.emit('command', data.toString()));
});

The first command, as well as in chat application, will be connect command.

main.on('help', () => {
  console.log('  write "connect IP:PORT" to connect to other nodes on the network.');
});

main.on('command', (text) => {
  if (text.startsWith('connect')) {
    const ipport = text.substr(8);
    const [ip, port] = ipport.split(':');

    console.log(`Connecting to ${ip} at ${Number(port)}...`);
    node.connect(ip, Number(port), () => {
      console.log(`Connection to ${ip} established.`);
    });
  }
});

Now I want the user to be able to search for the files first. I will only implement the search by name, but you can add other parameters in this command as well. Also the index does not help us looking for files at all, but we will use it later, I promise.

main.on('help', () => {
  console.log('  write "search FILENAME" to look for files.');
});

// Once the command arrives, we broadcast the search message on the network
main.on('command', (text) => {
  if (text.startsWith('search')) {
    const searchRequest = text.substr(7).trim();

    console.log(`Searching for file by "${searchRequest}"...`);
    node.broadcast({ type: 'search', meta: searchRequest });
  }
});

// Once we receive this message (on another node), we reply with results
node.on('broadcast', ({ origin, message: { type, meta }}) => {
  if (type === 'search' && origin !== node.id) {
    for (let key of index.keys()) {
      const data = index.get(key);

      if (data.name.toLowerCase().includes(meta.toLowerCase())) {
        node.direct(origin, { type: 'search/response', meta: data });
      }
    }
  }
});

// Once we receive the response from the file holder, we display it
node.on('direct', ({ origin, message: { type, meta: { name, size, hash } }}) => {
  if (type === 'search/response') {
    console.log(`  ${name} ${formatSize(size)} ${hash}`);
  }
});

This ping-pong style flow is easy to implement, but feels unstable as we, in theory, can receive search/response when no search has been issued, and it still trigger the console.log. I don't consider this an issue, but a safety check here won't hurt.

The next thing I want to do is that I want the user to be able to start download. Since hash is used for the index, we can use that as command's param, which makes sense (like you can create magnet links with file hashes and ask the application to download that without performing a search).

I don't know what I will do when download start right now, so I leave a socket there.

main.on('help', () => {
  console.log('  write "download HASH" to start downloading file');
});

main.on('command', (text) => {
  if (text.startsWith('download')) {
    const hash = text.substr(9).trim();

    main.emit('download', hash);
  }
});

In order to download file, we should establish a separate TCP connection to the peers and request chunks of data from them. The amount of chunks and the file name are not the information we have locally, even though we may have received it through search command, it's not guaranteed. So first of all, I want to setup a ping pong flow to exchange file meta information before starting download. It will be kinda the same as search flow, but in the end I will store the exchanged information in downloads and emit events once they change.

As you can see, the exchange information also contains the IP address of a seed, so I can connect to it's file server while downloading later.

const downloads = {};

main.on('download', (hash) => {
  node.broadcast({ type: 'download', meta: hash });
});

node.on('broadcast', ({ origin, message: { type, meta } }) => {
  if (type === 'download' && origin !== node.id) {
    const data = index.get(meta);

    if (!!data) {
      node.direct(origin, { type: 'download/response', meta: { ip: Array.from(node.addresses)[0], hash: data.hash, size: data.size, name: data.name } })
    }
  }
});

node.on('direct', ({ origin, message: { type, meta } }) => {
  if (type === 'download/response') {
    if (!downloads[meta.hash]) {
      downloads[meta.hash] = {
        hash,
        name: meta.name,
        size: meta.size,
        seeds: [meta.ip],
        chunks: [],
      };

      main.emit('download/ready', meta.hash);
    } else {
      downloads[meta.hash].seeds.push(meta.ip);
      main.emit('download/update', meta.hash);
    }
  }
});

Okay, now it's time to create TCP server that will react on file data requests and send data. We will exchange data in chunks, so the file server will only need to react on one specific type of message and send one type of message back.

const FILES_SERVER_PORT = 9019;
const CHUNK_SIZE = 512;

const filesServer = net.createServer((socket) => {
  socket.on('data', (data) => {
    const { hash, offset } = JSON.parse(data);
    const meta = index.get(hash);

    const chunk = Buffer.alloc(CHUNK_SIZE);
    const file = await open(meta.path, 'r');

    await file.read(chunk, 0, CHUNK_SIZE, offset * CHUNK_SIZE);
    await file.close();

    socket.write(JSON.stringify({ hash, offset, chunk }));
  });
}).listen(FILES_SERVER_PORT);

Alright, now it's time to implement actual download. I'll start by reacting to download/ready event and making an async loop, that will fetch chunks from seeds in parallel, one chunk by one seed at a time, but you can definitely tweak that.

In order to keep track of what chunk what state is, I fill the chunks field of the meta information with it's status and socket it is using to download data from.

main.on('download/ready', async (hash) => {
  downloads[hash].chunks = [...new Array(Math.ceil(downloads[hash].size / CHUNK_SIZE))].map(() => ({ state: 0 }));
});

In addition to that, I need a temporary file to keep the download, let's assign it and create a file handle for it.

downloads[hash].path = path.resolve(DOWNLOADS_PATH, `${hash}.download`);

const file = await open(downloads[hash].path, 'w');

Now I need to connect to IP addresses provided in downloads I know that once download/ready event is triggered, there are already some, but I also have to react to download/update events to update the list. I attach a listener to this event and detach it when download is finished.

const sockets = {};

const updateSocketsList = async ($hash) => {
  if ($hash !== hash) {
    return;
  }

  for (let ip of downloads[hash].seeds) {
    if (!sockets[ip]) {
      const socket = new net.Socket();

      socket.connect(FILES_SERVER_PORT, ip, () => {
        sockets[ip] = { socket, busy: false };
      });
    }
  }
};

updateSocketsList(hash);

main.on('download/update', updateSocketsList);

// ... TODO

main.off('download/update', updateSocketsList);

The main cycle is pretty simple, I look for an available chunk (chunk state 0 is ready, 1 is being downloaded and 2 is already downloaded) to download and a socket, that is not busy. If there is no socket (meaning all of them are busy) or no chunk (meaning they all are being downloaded), I just continue after 50ms delay. If both available chunk and socket are presented, I download, but do not await for this download to finish.

while (!!downloads[hash].chunks.find((chunk) => chunk.state !== 2)) {
  const availableChunkIndex = downloads[hash].chunks.findIndex((chunk) => chunk.state === 0);
  const availableSocket = Object.values(sockets).find(({ busy }) => !busy);

  if (!availableSocket || !availableChunkIndex) {
    await new Promise((resolve) => setTimeout(() => resolve(), 50));
    continue;
  }

  availableSocket.busy = true;
  downloads[hash].chunks[availableChunkIndex].state = 1;

  ;(async () => {
    const chunk = await downloadChunk(availableSocket.socket, hash, availableChunkIndex);

    await file.write(Buffer.from(chunk), 0, CHUNK_SIZE, availableChunkIndex * CHUNK_SIZE);

    downloads[hash].chunks[availableChunkIndex].state = 2;
    availableSocket.busy = false;
  })();
}

As you can see, I only have to implement the downloadChunk function that will actually grab data from socket. I want it to be an async function, while socket is an event emitter, so I need to do the following:

const downloadChunk = (socket, hash, offset) => new Promise((resolve) => {
  socket.write(JSON.stringify({ hash, offset }));

  const listener = (message) => {
    if (hash === message.hash && offset === message.offset) {
      resolve(message.chunk);
      socket.off('data', listener);
    }
  };

  socket.on('data', listener);
});

Now I only need to cleanup by closing the file handle, renaming the temp file to whatever the filename it should have, removing listeners to download/update and closing seed sockets.

await file.close();
await rename(downloads[hash].path, path.resolve(DOWNLOADS_PATH, downloads[hash].name));

main.off('download/update', updateSocketsList);

for (let { socket } of Object.values(sockets)) {
  socket.destroy();
}

This is how you can make a simplest Torrent application in less that 300 lines of code with Node and swenssonp2p. Full code of this app can be found here.

Create a P2P network with Node from scratch.

Aleksandr Churbakov — Wed, 30 Mar 2022 20:45:59 +0000

The best way to learn stuff in development is go and try to create your own whatever it is. In this article I'll walk you through creating a minimal example of unstructured untrusted peer to peer network using Node JS. I hope it will make you understand them better.

Basically P2P network is an abstraction based on a subset of nodes of underlaying network (TCP/IP for example), where all of the nodes are (in)directly connected to each other and equipotent (meaning they have the same role on application level, in oppose to server/client model).

In order to implement that, I be using net node module to establish connection and exchange information between nodes. In the end we'll make the simplest p2p chat application.

First of all, I want to define an interface of the library. As a consumer, I would like to get a function, that startups a node and returns a function, that stops it. Somewhere in the options, passed to that function I would like to handle the messages and do other stuff.

const net = require('net');

module.exports = (options) => {
  // start the node
  return () => {
     // stop the node
  };
};

Now, to begin, I need to setup a server to accept connections from peers.

const handleNewSocket = (socket) => {
  // peer connected

  socket.on('close', () => {
    // peer disconnected
  });

  socket.on('data', (data) => {
    // message from peer
  };
};

const server = net.createServer((socket) => {
  handleNewSocket(socket);
});

In order to understand, who is connected where and be able to send messages to those peers, I would like to keep them somewhere. To do this, I assign every connected socket with an ID and store them in a Map. The implementation of randomuuid is up to you.

Plus I know, that later, when I'll be implementing more logic I may need to catch the moment new connection is established, as well as the moment data arrives, but I don't know what I should put in there, so I leave a "socket" by emitting events for those cases. I will agree with myself, that I will only send JSON data to peers, so I also insert parsing code in there.

const EventEmitter = require('events');

const emitter = new EventEmitter();

const handleNewSocket = (socket) => {
  const connectionId = randomuuid();

  connections.set(connectionId, socket);
  emitter.emit('connect', connectionId);

  socket.on('close', () => {
    connections.delete(connectionId);
    emitter.emit('disconnect', connectionId);
  });

  socket.on('data', (data) => {
    try {
      emitter.emit('message', { connectionId, message: JSON.parse(data.toString()) });
    } catch (e) {
      // console.error(`Cannot parse message from peer`, data.toString())
    }
  });
};

After I have my server setup done, I can create a method that actually connects to other peers by making new sockets. It's a bit unusual to think "as server" and "as client" at the same time within one application, but P2P application actually are TCP servers and clients at the same time.

I will use handleNewSocket to treat outgoing connections as there is no difference to me whether the connection is outgoing or ingoing. And I will create a send method that will directly send a message to a specific connection.

const send = (connectionId, message) => {
  const socket = connections.get(connectionId);

  if (!socket) {
    throw new Error(`Attempt to send data to connection that does not exist ${connectionId}`);
  }

  socket.write(JSON.stringify(message));
};

const connect = (ip, port, cb) => {
  const socket = new net.Socket();

  socket.connect(port, ip, () => {
    handleNewSocket(socket);
    cb();
  });
};

After I have my connect method implemented, I only need the server to start listening to connections and I should be good to go. If you want, you can add a listener to an event when server is ready, I just didn't need that one.

server.listen(options.port, '0.0.0.0' /* add options.onReady */);

return (cb) => {
  server.close(cb);
};

Okay, I can connect to peers, but what if I want to send data over them? To someone I am not connected to? Well, first of all, I need to identify them. To do so, every node has to have its own uniq name. I cannot use connection ids as they may be different for the same node, plus they can be closed and open simultaneously due to rebalancing, for example.

To proceed, I need to create a second layer, that introduces the Nodes concept. Every Node will have its own uniq ID, that is defined by the Node on the startup. Once connection is established, the Node will send a specific message to its peers introducing itself. Peer Nodes will have to put their neighbor in a collection and introduce themselves too.

I'll listen to connect event to figure out when new connection is established and make the node introduce itself. Since this event is emitted for both outgoing and ingoing connections, I don't need to reply to that, both nodes on both sides of connection will receive that event.

const NODE_ID = randomuuid();
const neighbors = new Map();

emitter.on('connect', (connectionId) => {
  send(connectionId, { type: 'handshake', data: { nodeId: NODE_ID } });
});

After that, just later below, I'll listen to messages coming from the connection and, if that message is a type of handshake, I'll store the node and it's connection in neighbors map. And, as in the code above, I will notify upcoming layers, that the new node has been connected.

emitter.on('message', ({ connectionId, message }) => {
  const { type, data } = message;

  if (type === 'handshake') {
    const { nodeId } = data;

    neighbors.set(nodeId, connectionId);
    emitter.emit('node-connect', { nodeId });
  }
});

And, in the very end, I'll listen to disconnect event to see when the connection to a peer is lost and remove the corresponding node from the list of neighbors. To do so, I will need to find a nodeId (key) by connectionId(value) in my map, so I'll make a helper for that.

const findNodeId = (connectionId) => {
  for (let [nodeId, $connectionId] of neighbors) {
    if (connectionId === $connectionId) {
      return nodeId;
    }
  }
};

emitter.on('disconnect', (connectionId) => {
  const nodeId = findNodeId(connectionId);

  if (!nodeId) {
    // Let you handle the errors
  } 

  neighbors.delete(nodeId);
  emitter.emit('node-disconnect', { nodeId });
});

And, lastly, I will treat messages from the connections, where I know the corresponding nodeId, a bit differently. I will agree with myself, that everything I send to Node is not only JSON, but a { type, data } object, where type is either handshake or message. I'm already handling handshake properly, so I only need to add message handling. The resulting code should look like this:

emitter.on('message', ({ connectionId, message }) => {
  const { type, data } = message;

  if (type === 'handshake') {
    const { nodeId } = data;

    neighbors.set(nodeId, connectionId);
    emitter.emit('node-connect', { nodeId });
  }

  if (type === 'message') {
    const nodeId = findNodeId(connectionId);

    // if (!nodeId) {
    //   oops
    // }

    emitter.emit('node-message', { nodeId, data });
  }
});

See that now I emit node-* events for the following layers to use instead of connect, disconnect or message as they have a different format and a bit different meaning. A node-message will have a specific ID that will stay the same even if reconnect happens.

I can now receive data from Node, but I can't send a data there, so let's make a method for it. Remember I agreed upon { type, data } format.

const nodesend = (nodeId, data) => {
  const connectionId = neighbors.get(nodeId);

  if (!connectionId) {
    // error treatment for you
  }

  send(connectionId, { type: 'message', data });
};

Great! I have connections to our neighbors established, I can send and receive data, I know who sent this data and the ID is persistent, let's actually implement a method to send data over them.

The first way to send the data over neighbors is to recursively broadcast. That means I will send a message to my neighbors, they will send this message to their neighbors (including me) and so on.

To eventually stop this process I should keep the track of all the messages I have broadcasted in a collection, so I will assign an ID to each message I send and put it to the Set. But what if the traffic is so big, so this Set is getting really big really fast?

To partially avoid that I can clean the Set once in a while, which may lead some messages I have already broadcasted to appear again. To protect from those scenarios I will track the time to live or TTL for each message, meaning it cannot be broadcasted more that N amount of times. This problem is really tricky, so I probably will make another article on that.

const alreadySeenMessages = new Set();

const p2psend = (data) => {
  if (data.ttl < 1) {
    return;
  }

  for (const $nodeId of neighbors.keys()) {
    nodesend($nodeId, data);
    alreadySeenMessages.add(data.id);
  }
};

const broadcast = (message, id = randomuuid(), origin = NODE_ID, ttl = 1000) => {
  p2psend({ id, ttl, message, origin });
};

Correspondingly, I have to listen node-message and, once a message arrives, broadcast it to the next nodes.

emitter.on('node-message', ({ nodeId, data }) => {
  if (!alreadySeenMessages.has(data.id)) {
    broadcast(data.message, data.id, data.origin, data.ttl - 1);
  }
});

Basically this is all about broadcasting, the very bare p2p network is already done, but I may also need to not only broadcast the data to everyone, but also to send a data to a specific node (direct message).

As you may suggest, since I may not have a direct connection to destination, the direct message will actually be a broadcast as well. It will only be the application layer that decides that this broadcast message should be ignored. To differentiate those 2, I will add type along id and ttl, which will be broadcast or dm correspondingly. (And yes, the full message body will be { type: '...', data: { type: '..', data: '...' }}, but we don't care about it since it's on underlaying abstraction levels).

const alreadySeenMessages = new Set();

const p2psend = (data) => {
  if (data.ttl < 1) {
    return;
  }

  for (const $nodeId of neighbors.keys()) {
    nodesend($nodeId, data);
    alreadySeenMessages.add(data.id);
  }
};

const broadcast = (message, id = randomuuid(), origin = NODE_ID, ttl = 1000) => {
  p2psend({ id, ttl, type: 'broadcast', message, origin });
};

const dm = (destination, message, origin = NODE_ID, ttl = 10, id = randomuuid()) => {
  p2psend({ id, ttl, type: 'dm', message, destination, origin });
};

emitter.on('node-message', ({ nodeId, data }) => {
  if (!alreadySeenMessages.has(data.id)) {
    if (data.type === 'broadcast') {
      emitter.emit('broadcast', { message: data.message, origin: data.origin });
      broadcast(data.message, data.id, data.origin, data.ttl - 1);
    }

    if (data.type === 'dm') {
      if (data.destination === NODE_ID) {
        emitter.emit('dm', { origin: data.origin, message: data.message });
      } else {
        dm(data.destination, data.message, data.origin, data.ttl - 1, data.id);
      }
    }
  }
});

And we're done! Let's adjust the function from the very beginning to provide the library consumer with some kind of interface and make a simple chat application with it. I decided to change the shape of returning object and simply include there everything I may need outside:

return {
  broadcast, dm, on: emitter.on, connect,
  close: (cb) => {
    server.close(cb);
  },
};

And now, making a p2p chat application should be as simple as the following:

const createp2pnode = require('./p2p');

const node = createp2pnode({ port: 8000 });

// connect to your peers here using node.connect(IP, PORT);

node.on('broadcast', ({ origin, message }) => {
  console.log(`${origin}: ${message}`);
});

process.stdin.on('data', (data) => {
  node.broadcast(data.toString());
});

That's it! A lot of topics remain uncovered, like structuring and balancing the network, protecting data that moves over the network, implementing DHTs, which I may tell you about in the future articles.

The code in this repo.