Geekly Articles each Day
📜 âŹ†ïž âŹ‡ïž

"Heroes of Might and Magic" in the browser: long, difficult and unbearably interesting

How to implement a game in the browser, in which years ago it stuck without any browser? What difficulties will you encounter in the process, and how can they be solved? And finally, why do it at all?

In December, Alexander Korotayev (Tinkoff.ru) told at the HolyJS conference how he made the browser version of Heroes. The video of the report has already appeared, and now we have also made a text version for Habr. To whom it is more convenient video - run the movie, and to whom the text - read it under the cut:


I would like to tell you about how I made those third “Heroes” in the browser, in which many of you, I think, played in childhood.
')
Before you take on any interesting long journey, you should see the route. I went to GitHub and saw that every two months a new clone of Heroes appeared. These are repositories with two or three commits, where literally several functions are added, and the person throws them, because it is difficult to do. He understands the entire burden of responsibility, which will fall on him, if this finish. Here I have provided links to the most successful repositories that can be found:

  1. sfia-andreidaniel / heroes3
  2. mwardrop / HOMM3Clone
  3. potmdehex / homm3tools
  4. openhomm / openhomm
  5. vcmi / vcmi

I singled out the last one to highlight its importance to the community, because it is the only fully written clone of “Heroes” in C, using the distribution of original resources that can be put to it. And this is the only way to run third “Heroes” on Android devices. They run through the emulator, the problem is that they are very slow, the touch-interface is not available there, you have to move the mouse - in general, this is only for very large fans.

What goals did I set for myself when I took it?


At first I tried to repeat the original image:



Below you can see the original editor and its simple render, and my simple render, which, however, cost without flags at that time. This is practically the first screenshot of the game development. By the way, it may also be useful for you to take screenshots of some of your own projects that will kill someone, because one day it may be necessary. I needed a screenshot for my report, although I didn’t plan on it initially, I just wanted to save the story. I thought it was a long story, and I should keep it in pictures.

And so, I almost repeated the picture of the original game, but I had to move on.

For a start, for those who are not aware of gamedev in JavaScript, I will tell you what a regular game consists of:


If we present this in the form of code, everything is simple:

01. const me = {name: 'Alex', left: 0} 02. ... 03. setInterval(() => update(), 1000) 04. ... 05. window.addEventListener('keyup', () => me.left++) 06. ... 07. requestAnimationFrame(() => draw())

What is behind this:


You can read more about game development on JS in the book “Surrealism on JavaScript” , open it at least for the sake of such wonderful pictures:




Brief history of game development


If you want to start making your “Heroes”, you have:

  1. Original game
  2. Map editor. The developers at first thought that he would allow the game to live for a maximum of two more years, how badly they were wrong!
  3. FizMig is a great reference for all game mechanics. Its remarkable fact is that people empirically calculated all probabilities of loss of skills, spells, any damage, and presented it in formulas and tables with a percentage ratio. People have been working for ten years, that is, they are very big fanatics, even I cannot compare with them.
  4. There are many forums with guys who have been digging in “Heroes” for many years. By the way, Russian-speaking forums: English-speaking guys almost did not dig.
  5. Resource unpacker, thanks to which you can get pictures, data, anything.

I started with rendering the usual green field, as in the first picture:



Here you can see how I drew objects on the green field and debugged their important points. Red dots - this is obstruction, yellow - some kind of action at this point. At the castle action is only where you can go, the hero is on the whole model.

Next, I worked with the data. Data is a list of all skills, monsters, characters, maps, everything related to text and binary files that you had to read and somehow accumulate.



Then I worked with algorithms. I did not get the algorithms right away. Here I tried to make a path finding algorithm:



But not everything worked smoothly, this is probably one of his best runs.

I realized how much I was wrong when I tried to write it myself. However, in my case nothing was going smoothly, in fact I was walking practically across the field from a rake. Fortunately, I did not give up and still tried to find a way out of this situation, and I somehow managed to do it.


Parsing maps


At the beginning there was a very important stage, it was relatively boring, difficult, and this is the parsing of maps. The fact is that if it were not for him, there would be nothing. Since it was not interesting for me to draw just a field with objects that I superimposed on each other with the help of some offset, I wanted to read the original maps in order to have a convenient editor with which you can immediately watch the changes in the game:



When you open a map in this editor, you see an excellent visual interface for editing any buildings, objects, and so on. It is convenient, understandable and intuitive. Many thousands or tens of thousands of cards for “Heroes” have already been made, there are still a lot of them.

But if you want to read it as a developer, you will see that this is just a binary code that is difficult to read:



I was meditating on this code, I found some poor specifications on how it works and what it has inside, and over time I even began to read it. I have been looking at it for literally two weeks, and I am already starting to see some regularities!

Then I realized that something was wrong with me, I started digging and found out that normal guys read this in editors with template support:



Templates have already been written for maps that allow them to be parsed in the 010 Editor. In it, they open as in a browser. You see something like dev-tools, you can hover over some section of code, and it will show what's inside there. This is much more convenient than the one I tried to work with earlier.

Suppose there are scripts, it remains to write the code. At the beginning I tried to do it in PHP, because I did not know another language that could cope with it, but over time I came across homm3tools . This is a set of libraries to work with different data "Heroes". Basically, this is a parser of various card formats, a map generator, a render of inscriptions from trees, and even a game "Snake" from game objects. When I saw this craft, I realized that with homm3tools you can do anything, and the fanaticism of this person lit me. I started to communicate with him, and he convinced me that I should learn C and write my converter, which I, in general, did:



In fact, my converter allows you to take a regular map file for “Heroes” and turn it into readable JSON. Readable for both javascript and humans. That is, I can see what is in this map, what data is there and quickly understand how to work with it.

The data became more and more, the number of objects grew, I ran all the big cards and saw that resources were leaking somewhere. They became smaller and smaller, and even a small movement on this map caused friezes and brakes. It was very unplayable and ugly.


Everything slows down!


What should I do about it? I never encountered this, and first went to look at the drawing of maps. The map is big, it probably slows down.

But first, a little theory. Since everything is drawn on Canvas, I would like to explain how it differs from the DOM. In the DOM, you simply take an element, you can move it, and you do not think about how it is drawn, just move it, and that’s it. To move and draw something on the canvas, you need to erase it every time:

 01. const ctx = canvas.getContext('2d') 02. 03. ctx.drawImage(hero, 0, 0) 04. ctx.clearRect(0, 0, 100, 100) 05. ctx.drawImage(hero, 100, 0) 06. ctx.clearRect(0, 0, 100, 100) 07. ctx.drawImage(hero, 200, 0)

If there is grass under the hero you are animating in this way, you have to draw grass:

 01. const ctx = canvas.getContext('2d') 02. 03. ctx.drawImage(hero, 0, 0) 04. ctx.drawImage(grass, 0, 0) 05. ctx.drawImage(hero, 100, 0) 06. ctx.drawImage(grass, 100, 0) 07. ctx.drawImage(hero, 200, 0)

This is even more expensive and even more complicated, and in the case of very complex backgrounds, this is a very difficult task at all.

Therefore, I propose to draw in layers:



You just take the layers, and mixes their video card, which is what it should do. So I saved a lot on redrawing, each layer is updated with its order, drawn at different times. I got a more or less fast render, with which you could really do something complicated.

I simply use three Canvas that are superimposed on each other:

 <canvas id=”terrain”> <canvas id=”objects”> <canvas id=”ui”>

Their names speak for themselves. Terrain - grass, roads and rivers.

If you look at the terrain drawing algorithm, it may seem quite loaded in terms of resources:

  1. Take soil type tile
  2. Draw it with offset and rotation, because the developers of the original game saved a lot on resources
  3. Impose river
  4. Impose road
  5. And there are still special soil types.

And all this needs to be rendered, and preferably not in runtime. Therefore, I advise you to draw it as soon as you make the first render of the map, and put it in the cache. Drawing finished pictures is much cheaper than drawing roads again each time you need them.

How to smoothly move the map? I had problems with this, but I came across a solution from Yandex.Map:



The fact is that when you move the map, it changes the transformation. This operation, as many know, is performed only on the video card, without causing Repaint. Quite a cheap operation to move a rather large picture. But every 32 pixels I compensate for the left of this card, in fact I’m just redrawing it, but the user has the impression of a continuous movement of the map. What I wanted to achieve, so implemented in Yandex.Maps, and so I implemented.

Then I started drawing objects, because the optimization of one map was not enough for me. But first, a little theory. The fact is that the axis of drawing objects in "Heroes" is inverted. In fact, objects are drawn from the bottom right corner. Why is this done? The fact is that we look at the map as if from above, but in order to give the player the impression that he is looking at three-quarters from the side, the objects are drawn from bottom to top, overlapping each other.



Algorithm for drawing objects:

  1. Sort an array of Y lower bound of each object (textures of different heights, you need to take this into account)
  2. We filter those that do not fall into the window (to draw what a person does not see is a little expensive)
  3. There are a lot of different checks.
  4. Draw the texture of the object
  5. If necessary, draw a flag player
    And this is all despite the fact that the number of objects can reach over 9000! What to do, how to draw it in runtime? I think that it is better not to draw it in runtime, and now I will tell you how.



    To begin with, I found a drawing algorithm such as renderTree. It is used, for example, in the browser to draw DOM elements that hang over each other with a Z-index. And each branch that is in this tree is the Y axis, by which the objects are sorted. In turn, on each branch all objects are sorted by the X axis.

    What do we get from this? We get a cheaper iteration, because we can immediately cut off branches that do not fall on the screen. And with each iteration of the branch, we will look at the X object, and as soon as we bump into an object that just does not fit in the map, we stop iterating over this object. Thus, fewer objects are affected than if we simply ran through the array. Also, we are immediately given the correct overlapping of objects, because they are already sorted. Thus, it turns out competent data storage.

    Next, I went to the drawing function:

     01. const object = getObject(id) 02. const {x, y} = getAnimationFrame(object) 03. const offsetleft = getMapLeft() 04. const offsetTop = getMapTop() 05. 06. context.drawImage(object.texture, x - offsetleft, 


    We see that each function consists of the fact that I define the final displacement of an object, its frame for animation, and, most importantly, the drawImage function. It all came down to this function, and it was necessary to somehow optimize it.

    I realized that I can simply create this function through bind with the necessary parameters and save it directly in the renderTree. That is, I stopped storing objects there, and began to store only the functions of drawing. There’s nothing more to do, so I got a great performance boost.



    But it’s not just the objects, it’s also that the game shouldn’t slow down in terms of animation. Konyashka should run around the screen perfectly, otherwise you will get the impression that there is something wrong with the game.

    Let's go into geometry a little bit to understand what we had to go through. There, when you lay a segment at a certain distance in any direction - even horizontally, even diagonally - they are equal.



    But this is geometry. And we have “heroic metric”. The problem there is that this is a game on a grid, where the diagonal and horizontal displacements in fact are not equal, but the game considers that it is equal, and everything is fine.



    How to live with it? If to count, then for horizontal movement we make four steps of animation, for diagonal - about six. I started looking for a solution on how to make this animation really smooth.

    The problem with JavaScript is that it is single-threaded and handles tasks. Each setTimeout that we set creates a separate task, it competes with other tasks that we have, for example, with other setTimeout. And in this regard, nothing will save us.

    I tried to do it through setTimeout, through setInterval, through requestAnimationFrame - everything creates tasks that compete with each other.



    And with a large number of calculations when a player moves, competing tasks spoil my entire animation.

    I went to look further and found that in JavaScript, it turns out, there are microtasks that are part of the tasks. They are needed in cases where the callback that you transmit to, say, in Promise, the only object that does the microtask can occur either immediately or asynchronously. Therefore, just in case, a microtask was implemented, which takes precedence over the task.



    In fact, we get a non-blocking loop that can be used for animation. Read more about this in Jake Archibald’s article .

    For starters, I took everything and wrapped it in Promise:

     01. new Promise(resolve => { 02. setTimeout(() => { 03. //    04. requestAnimationFrame(() => /*  */) 05. resolve() 06. }) 07. })

    I still needed setTimeout to do the animation, but it was already in Promise. I did the calculations for the animation and fed to the requestAnimationFrame function what I needed to draw on the basis of these calculations so that the calculations did not block the drawing, and it went when it was really necessary.

    Thus, I was able to build a whole sequence of animation steps:

     01. startAnimation() 02. .then(step) 03. .then(step) 04. .then(step) 05. .then(step) 06. .then(doAction) 07. .then(endAnimation)

    But I realized that this object is not very configurable and does not strongly reflect what I want. And I thought of storing animations in an object called AsyncSequence:

     01. AsyncSequence([ 02. startAnimation, [ 03. step 04. step 05. ...], 06. doAction, 07. endAnimation 08. ])

    In essence, this is a kind of reduce, which is traversed by the Promise and calls them sequentially. But it is not as simple as it seems, the fact is that it also has nested animation loops. That is, after startAnimation, I could thrust an array from one step. Suppose there are seven or eight of them, as much as you need for the diagonal animation of the hero.

    As soon as the hero reaches a certain point, the reject comes out in this animation, the animation stops, and the AsyncSequence understands that it is necessary to switch to the parent branch, and there already the doAction and endAnimation is called. It is very convenient to do complex animation declaratively, as it seemed to me.


    Data storage


    But not only thanks to the renderer we can increase our productivity. It turned out that most of all it slows down the storage of data, which was for me the greatest surprise in JavaScript.

    To begin with, we find the data that is most inhibited, and this is a map. The whole map is a grid, it consists of tiles. Tiles are some conditional small squares in the grid that have their own texture, their own set of data, and allow us to build a map from a limited number of textures, as all the old games did.

    This data set contains:

    1. Type of tile (water, earth, wood)
    2. Passability / cost of moving the tile
    3. Presence of an event
    4. Flag "Who is busy"
    5. Other fields depending on the implementation of your engine

    In the code, this can be represented as a grid:

     01.const map = [ 02. [{...}, {...}, {...}, {...}, {...}, {...}], 03. [{...}, {...}, {...}, {...}, {...}, {...}], 04. [{...}, {...}, {...}, {...}, {...}, {...}], 05. ... 06. ] 07.const tile = map[1][3]

    The same visual design as the tile grid. An array of arrays, in each array we have objects that contain something for the tile. We can get a specific tile by offsetting X and Y. This code works, and it seems to be normal.

    But. We have an algorithm for finding a path, which in itself is quite expensive, it has to take into account the mass of details that are not only in the tiles, but also in the objects. And when we move the mouse, the cursor changes depending on whether we can reach this point, whether the opponent is at this point or some kind of action.



    For example, hovering on a tree - a regular cursor appeared, because it is impossible to pass to this point. And we need to show the number of days it takes to get to the point. That is, in fact, we are chasing the pathfinding algorithm all the time, and that same grid works very slowly.

    To get the tile property, I needed:

    1. Request an array of tiles
    2. Request array array for string
    3. Request Tile Object
    4. Request Property Property

    The four heap calls, as it turned out, are very slow when we need to request a map so many times for the pathfinding algorithm.

    And what can you do about it? At first, I looked at the data:

     01. const tile = { 02. //    03. render: {...}, 04. //     05. passability: {...}, 06. //      07. otherStuff: {...}, 08. }

    I saw that each tile object consists of what is needed for the render, what is needed for the pathfinding algorithm, and other data that is needed much less frequently. They were called each time, despite the fact that they were not needed. It was necessary to discard these data and figure out how to store them.

    And I found that the fastest way to read this data is from an array.



    After all, a tile object can be divided into arrays. Of course, if you write the business code at work, there will be questions for you. But we are talking about performance, and here all the means are good. We just take a separate array, where we store the type of the object in the tile, or that the tile is empty, and with it an array of numbers for the algorithm for finding the path, which is a simple unit / zero "cell is passable or not."

    But for the path finding algorithm, you need not only to find out if there is an object or not, and put a one or zero. Different types of soil have different permeability, different characters walk differently, all this must be considered.



    This simple array is calculated by complex algorithms of two large arrays: with tiles and with objects. Thus, we get the already calculated numbers that can be quickly used in the path finding algorithm. We consider in advance when the object is updated, update and value.

    As a result, we have a lot of arrays that cache and bind something:

    • An array of drawing functions for the drawing cycle
    • Array of numbers to find the way
    • Array of strings to associate objects to tiles
    • Array of numbers for additional properties of tiles
    • Map of objects with their ID for game logic

    All that remains is the timely update of data from slow to faster storage.

    Of course, the question is how to get away from an array of arrays, which is much slower than a regular array.

    In fact, I switched to a regular array, just by expanding the array of arrays, it works 50% faster:



    Getting data offset in an array is simple. Y, , , X.

    Further more. , X Y . - , , X Y, - :

     01. const map = [{...}, {...}, {...}, {...}, ...] 02. 03. const tile = map[y * width + x] 04. map.forEach((value, index) => { 05. const y = Math.floor(index / width) 06. const x = index - (y * width) 07. })

    , , . , , , .

    :



    «Power of 2», « » « », , . , , .

    , -, , , , . , .

    , , , , , , , , , , .

    , , , , , , - , .

     01. const map = [{...}, {...}, {...}, {...}, ...] 02. const powerOfTwo = Math.ceil(Math.log2(width)) 03. 04. const tile = map[y << powerOfTwo + x] 05. map.forEach((value, index) => { 06. const y = index >> powerOfTwo 07. const x = index - (y << powerOfTwo) 08. })

    , 50x50, 50 ( X Y, ).

    , :



    , MIP-, - , . , , , .

    Grid. Grid — , , X Y , , , X Y.

     01. const grid = new Grid(32) 02. 03. const tile = grid.get(x, y) 04. grid.forEach((value, x, y) => {})

    , , , . , , 256: , , . , . , 256x256, .


    UI Canvas


    UI Canvas. , , , UI HTML. , , . .

    , - , eventListener. , - .

     01. const okButton = new Buttton(0, 10, 'Ok') 02. okButton.addEventListener('click', () => { ... }) 03. const cancellButton = new Buttton(0, 10, 'Cancel') 04.cancellButton.addEventListener('click', () => { ... })

    , , . «» , .

     01. const okButton = new Buttton({ 02. left: 0, 03. top: 10, 04. onClick: () => { ... } 05. }) 06. const cancellButton = new Buttton({...})

    , , JSON.

     01. [ 02. { 03. id: 'okButton', 04. options: { 05. left: 0, 06. top: 10, 07. onClick: () => { ... } 08. }, 09. },

    , , . , . , . , , , .

    , XML. XML — , HTML, , JSON, , .

     01. <button id="okButton" 02. left="0" 03. top="10" 04. onClick="{doSomething()}" 05. />

    , . , .

    , , , , . , .

     01. <group id="main" ... > 02. <group id="header" ... > 03. <text-block ... /> 04. <button ... /> 05. </group> 06. <group id="footer" ... > 07. <any-component ... /> 08. <button ... /> 09. </group> 10. </group>

    , , — XML - Canvas. — react-canvas , , , - , - , .



    , , , 
 , : ? - :



    , , , , - , - , — . , - , .

    . — , . , , , . , , , . , .

    , , . - , . ?

    :



    A*. . — , , , , . , — , . «» ( , , , , ).

    , , . . Why do you need it? , , , , , :



    , , .

    , , , :

    • ID
    • : ,
    • ID
    • ,

    , , PubSub events:

     01. const objectInAction = Objects.get(ID) 02.const hero = Player.activeHero 03. objectInAction.events.dispatch('action', hero) 04. ... 05. this.events.on('action', hero => { 06. hero.owner.resources.set('gems', this.value) 07. this.remove() 08. })

    , , callback ( «action» , — . , ).

    , , , , :

    • -,
    • ( , save/load, , )

    , . , , — 10%, , , . , 90% , , - . , , , .

    , . , , , , . . , ? , , - , ?

    ? , :

     01. //        02. @Mixin(Attacable) 03. class TownObject extends OwnershipObject {...} 04. //     ,    .. 05. class OwnershipObject extends MapObject {...} 06. //        07.class MapObject {...}

    , - . , - . , TownObject, , Attacable, . , , , , , , ( , , , ).

    TownObject OwnershipObject, , , . , , , , - . , , MapObject, , .


    findings


    ? . , , , (, ). , , . , , , - , .

    : ? . , - ? , , , , : « webpack - , ». , , , . , !

    :

    • . , , , web-, , , , , , .
    • , , .
    • , - «». , - . - , - . , , , , . .

    :

    • , , , ,
    • , . , , , , , , , , .
    • . , , .

    , , . , , , , . , . , , 50, , .

    , , . , , , - . , . ́ .

    , :


    , , , . .
    Minute advertising. HolyJS, : 19-20 HolyJS 2018 Piter . , , !

Source: https://habr.com/ru/post/354014/

More articles:


All Articles