The idea of ​​the game and its features

Probably everyone played some games where words should be composed. Who does not know what crosswords are? And Cities .? Another popular game (I do not remember the name) - a long word is given (for some reason I remember “electrification”), and all sorts of words (“electrician”, “fiction”), etc. are made up of it. In general, there are a lot of such games - as well as classic (nastolki, sheet and pen), and electronic.

But we are always not enough, we want more and better, right?

In the West, there is a popular board game, where you also need to make words. Called Scrabble, here is more information . The rules are simple - on the square playing field there is initially one word. Each player has certain letters. In his turn, he must lay out one chip so that a new word (or several words) is obtained. Each letter has its own value (in points), so some words are more valuable than others. Rare letters (for example, "F") give more points.

My friend played a lot in Scrabble, and he had an idea - why not change the rules of the game so that it becomes more dynamic? In short, it sounds like this - add one letter to one and collect a new word.

No sooner said than done.

Example: there is a playing field where the word "LAZ" is. Add the letter "K" - we get the word "LAC". Very simple, isn't it?

Some game restrictions: you can only make nouns, remove their own names, place names, names, etc. Words that can only be used in the plural are left (for example, "glasses").

I made a prototype of the game for a couple of days, and it fascinated me. With a terrible design, with an incomplete vocabulary, with a blunt AI - but it was playable and addictive.

And I took seriously the development.

Iron opponent

How does the development of the game begin? In our case - with a playable core, which can be expanded. We have a game with a computer.

In general, we planned several game modes. But the first mode, which should be in any case - is a game against the computer. Live opponents may not be close, and here our computer will help out. So I started writing the game by writing artificial intelligence (AI).

How does AI work in our game when it moves?

The first stage is the search for extreme cells. I called a cell by a cell that contains a letter and has at least one free cell vertically or horizontally. In the picture below, these cells are highlighted with red dots.

Why do we need such cells? And because we can deliver a letter to an empty cell (yellow dot), and get a new word. Please note that the word can be collected in two ways. You can put a letter, start with it, and collect the word GAS (G first). Or put the letter of the last, and collect the word ASS (last).

The second stage is after we have found all the extreme cells. The next task is to make all kinds of chains, and check whether we can make a new word by adding a new letter in front or behind. For example, for the example in the picture above, the following chains are possible:

• L
• LA
• LAZ
• BUT
• LA
• AZ
• H
• BEHIND
• HALL

Obviously, as the field increases and the field becomes full, the number and length of the chains will increase. Therefore, a willful decision was made, even at the maximum level of difficulty, to limit the length of strings to 10 characters. As practice has shown, even with such a restriction, a computer without any problems cracks down on a person (at least with me and my friend).

The third stage is to check which chains are valid (that is, you can create a new word). I think, you guessed it, what problem seems obvious - we cannot use a dumb search, there are not enough resources to compare millions of times a line (if you search, just sorting through the elements sequentially). It immediately comes to mind to use binary search - the benefit is a dictionary, and we can compare words.

So I did. True, I still optimized it. What is the point - I slyly sorted out the dictionary. For example, we have a string of 5 characters in length. Obviously, the new word will be exactly 6 characters long. That is, the length of the chain, we know the exact length of the word. Therefore, the dictionary is sorted first by word length, and inside - alphabetically.

Here is an example. We have a chain SA. If we add the letter D to the end, we get the word SAD, which is very good. Therefore, what we do:

• look for all words in the dictionary, 3 letters long (chain length + 1)
• among these words, we are looking for everything that begins in SA

The attentive ones noticed that this way we can find only those words that can be made up by adding a letter to the chain at the end. But what about those words that can be made up by adding the letter at the beginning of the chain? After all, we can make a word, and adding a front letter - for example, OCA. It turns out that we need to look for three-letter words that end in the CA dictionary and we don’t have a sharpened word for it.

The output was another dictionary, which is also sorted first by word length, and then by SECOND letter of the word. Here is an excerpt from our dictionary:

...
yard
orc
ruff
wasp
claim
axis
oak
tooth
cube
...

It turns out that in both cases we are not looking for a complete word, but a substring (chain).

And finally, the final stage is the sorting of the words obtained according to their price (and the price is calculated as the sum of points multiplied by the word length), and issuing the result depending on the complexity.

About the complexity. There is a good phrase - the task of the AI ​​is not to win, but to give up nicely. In this case, this phrase is fully justified. Writing an AI to play to the fullest means a person’s crash, binary search and modern smartphones do a quick search of options. Therefore, the computer has a certain framework - it must keep from a person + - a certain number of points. There are additional points there - for example, he cannot collect words that are less than a certain value.

By the way, in the Ultra mode, all restrictions have been removed from the computer. If someone knows a lot of long words with the letters b, f, b - play, it will be an interesting duel.

Another life hack available to a person, but not available to the machine. You can make a word, and adding a letter in the middle of the word. For example, we have a chain M * MA (an asterisk is an empty cell). If we add asterisk A instead of - we get the word MOM. So, the computer is not looking for it - use it, fool the piece of iron (I do this all the time).

As a conclusion, I want to say the following. I was afraid that the AI ​​would slow down - and initially undertook to optimize it to the maximum - no strings, arrays of chars, binary search with optimizations for a specific task. But nothing slowed down - in general. That is, even my ancient android-smartphone without delay works out the tasks of enumeration, even in a large field. Conclusion - not such a weak iron on smartphones.

Game model. Work with dictionaries

The first thing you need in games of this kind is a dictionary. The more complete it is, the less problems there will be from angry users. And if there is no rare word, this is not a big problem. And if there is no word "cat" - this is very bad. Therefore, the first stage is the compilation of a dictionary. Oh, yes, two dictionaries - the game is in Russian and in English.

First, I went through the Internet, found a base of 37 thousand words. I was delighted. But early. This base was the result of a parser written by the author a long time ago. As a result, there were not many words, and many were inappropriate (there were proper names, and — oh, horror — adjectives). That was bad. My friend threw me a couple more files with the words - there it was even worse - there were numbers, and everything like that.

I wrote a utility in java, which I give to the input a "junk" file with all the words, and I give a list of valid characters. And she throws out repetitions from the dictionary, removes words that have the wrong letters, cuts off too long words (hardly anyone will make a word more than 15 letters in such a game), and sorts them in alphabetical order (not quite alphabetic, but about this later). After that, life became easier. There was a new portion of words - added them to the end of the "junk" file, launched the utility - at the output ready-to-use words.

I want to say that how many we did not look for dictionaries, we did not find all the words (and probably we will never find it again). We played a lot of the game ourselves, and constantly wrote words on the leaflet, which I then manually added to the game. This process continues even now - even though we find new words less and less. I suspect that we just have limited vocabulary :)

The next stage - we had a dictionary, where there were many, many words, and there were such words about which we did not know anything (do you know what is TPP? And this is such a variant of the pace, the horse jumps like that. I did not know personally, alas ). What to do with these words? Just throwing is not an option, because there are people who are smarter than me and my friend, and know what this beast is a CTP. Therefore, in a couple of hours I’ve put a utility on the left which is a list of words, and on the right a browser for the highlighted word:

A special feature is English. Half of the words there are both nouns and half of the parts of speech. And since neither I nor my friend are native speakers, it was difficult for us to work with such a dictionary. We limited ourselves to checking short words (up to 5 letters inclusive) to en.wiktionary, so that there were noun. In general, the approach is not very, but we have thrown out the worst words (like uivag). Immediately to the question, where did such a word come from - this is not me, this is a parser so put on, and then we were disentangling :).

We are well aware that the dictionaries have the wrong words, and we slowly clean the dictionaries. But what about those words that are not included in the dictionary, and people enter them? The decision was on the surface - if a person collects a word that is not in the dictionary, I send it to Google Analytics. The plan is simple - we export the data as csv, I write software that will subtract the unique words from this stream. The same software maintains a database where we will mark the words as scanned (if we are sent the word SHELF 768 times, I will be addicted 768 times to add it). And little by little we will improve our vocabulary.

Also in the next update we will add the ability to maintain a user dictionary. If the user is exactly sure that such a word is in the dictionary, but we do not have it - he will be able to add this word.

I also wanted to take ready-made dictionaries (in dict format), and some libraries for working with them. Perhaps for other languages ​​we will do that. But, I am afraid, even in this case we will not cover 100% of all the necessary words of the language.

In general, dictionaries - it is very difficult. More precisely, a bad dictionary is generally easy, but a good dictionary is generally difficult. It won't be done the first time, and we are now at the stage of constant improvement.

Design

Design is hard. Design is not mine.

A friend has an artist who drew us what you see in the screenshots. This is not the gloss that you see in Candy Crush. On the other hand, the current style is nice looking and suits this type of game. I am pleased with the design.

As expected, there are some problems between the design and its size. I made the most of the large backgrounds, saved them in jpeg - I saved the size of apk, but did not improve anything on the video card. But I did the maximum 9patch interface elements. So I got about the same display on different screens.

If you open the game, and open any dialog box - this is 9patch. Both the blue background and the buttons are 9patch. For myself, I realized that I would insist on 9patch as much as possible where it is possible.

But the picture for those who can not open the game:

Apparently, we won.

First version - Unity3d

I started writing on Unity3d. I had a little experience (before that we released another toy on Unity3d, but that's another story), and the 5th version is free, and the cool UI system is from the box ... In general, I was tempted.

What to say. The game slowed down. Everything is OK on the computer, but on the phone there were always small lags, even though I didn’t do anything. At first I sinned on non-optimized, but closer to the release I was worried - everything seemed to be playable, but small such lags spoiled the whole raspberry. And I started digging optimization materials.

I originally measured FPS. He was bad - he jumped. From 10 to 60. When he was 10 - play was bad, scrolling the panel with letters was fuzzy and jerky. I was upset and began to apply all the advice from the Internet. I degraded the quality of the textures, raised the V-sync, set lower quality settings. I forcibly set compatibility only with OpenGL 2 (wrote that it helps). In general, I tried everything I could.

Then I did the following - I created a new empty scene. There put the FPS counter. And launched the game. The FPS was about 50 - I was a little upset, because for some reason the empty scene already eats 10 frames - but not very much, because he (FPS) almost didn’t jump. After that I added Canvas to the scene, added Image (full-screen background 480 * 800, of the most primitive shader - it seems, Vertex Unlit) - and launched it again. FPS dropped to 40. I was generally upset.

I had no problems with the architecture of the game, C # is similar to java, in some places even more comfortable (hello, properties), and in some places worse (there is no such freedom in working with enums). I wrote all the code without problems, I did the whole UI. But I could not do anything with the brakes. I rummaged on the Internet, and found a bunch of similar problems in other people. They wrote that after the appearance of the 5th version of Unity3d, their projects began to slow down terribly. Apparently, I am another victim. I tried to install Unity 5.2 (I originally had 5.3), tried it and beta 5.4. To no avail.

I was disappointed in Unity3d, the hope of releasing the game in a day or two collapsed. I could not release a braking puzzle game, the inner one in me did not let me do it. I decided to go back to basics.

Switch to libgdx

I created a new libgdx project, and started porting the game. libgdx is something that did not let me down. Some things to do there longer (because everything is handles), but I have never had any questions about performance.

The architecture turned out, of course, quite different than on Unity3d. The only part that I transferred without changes is working with dictionaries and AI. I stupidly copied files from Unity3d, changed the extension from .cs to .java, and corrected the code. And it worked fine. This proves that language is not important - the algorithm and the idea are important.

I made the main class a singleton, and called it Core:

private SpriteBatch batch; private Assets assets; private Localize localize; private WordDict dict; private PlatformInteraction platformInteraction; private SolutionSearcher searcher; private float appTimeInSeconds = 0f; private Core() {} public static Core getInstance() { return instance; } public void setPlatformInteraction(PlatformInteraction platformInteraction) { this.platformInteraction = platformInteraction; } public PlatformInteraction getPlatformInteraction() { return platformInteraction; } @Override public void create () { batch = new SpriteBatch(); assets = new Assets(); assets.loadAll(); localize = new Localize(); localize.loadLanguage(Settings.getInstance().getLanguage()); dict = new WordDict(); dict.load("en"); searcher = new SolutionSearcher(); searcher.setDict(dict); Gdx.input.setCatchBackKey(true); setScreen(new SplashScreen(batch)); } public SpriteBatch getSpriteBatch() { return batch; } public TextureRegion getRegion(String regionName) { return assets.getRegion(regionName); } public BitmapFont getFont(int size) { return assets.getFont(size); } public String text(String tag) { return localize.text(tag); } public Localize localize() { return localize; } public WordDict getDict() { return dict; } public Assets assets() { return assets; } public SolutionSearcher getSearcher() { return searcher; } @Override public void render() { appTimeInSeconds += Gdx.graphics.getDeltaTime(); super.render(); } @Override public void dispose() { platformInteraction.reportGameEvent("app-session-length: " + (int) appTimeInSeconds + " sec"); super.dispose(); } 

Wrote the base class for all screens:

 class BackPressListener extends InputListener { @Override public boolean keyDown(InputEvent event, int keycode) { if (keycode == Keys.ESCAPE || keycode == Keys.BACK) { onBackOrEscapePressed(); return true; } return false; } } public BaseScreen(SpriteBatch batch) { if (batch == null) { batch = new SpriteBatch(); } stage = new Stage(new ScreenViewport(), batch); stage.addListener(new BackPressListener()); } @Override public void render(float delta) { Gdx.gl.glClear( GL20.GL_COLOR_BUFFER_BIT | GL20.GL_DEPTH_BUFFER_BIT ); stage.act(delta); stage.draw(); } @Override public void show() { Gdx.input.setInputProcessor(stage); } public void addActor(Actor actor) { stage.addActor(actor); } public void onBackOrEscapePressed() { } public Stage getStage() { return stage; } public SpriteBatch getBatch() { return batch; } public void postTask(float delay, Runnable task) { stage.addAction(Actions.sequence(Actions.delay(delay), Actions.run(task))); } public void repeatTask(float interval, Runnable task) { stage.addAction(Actions.forever(Actions.sequence(Actions.run(task), Actions.delay(interval)))); } public float getHeightPixels(float percent) { return stage.getHeight() * percent; } public float getWidthPixels(float percent) { return stage.getWidth() * percent; } 

I also made some auxiliary classes - as a typesetter, localizemanager. These are trivial things, it makes no sense to describe them even. I take localization from json files. I would like to note that the latest libgdx versions allow you to make text colored, marking it with [COLOR] tags. We just needed to do this (in one Label, to make several colors), and this opportunity came in very handy.

The game is logically divided into 4 screens (splash, initial choice of language, menu, game screen). Each screen is a separate package, if possible, elements of the screen are separate classes (for example, there is a menu screen, and there is a top panel - I make this panel a separate class). Then it's easier to rule the toy.

If possible, the logic is in the Model class. It stores the state of the field, a list of words that have already been used. The model also sends messages if there are any changes in it. It turned out about the pattern Model-Presenter. Presenter is a GameScreen, which shows the image and handles user input.

To support multi-screen, I used Table. Who does not know - this is the layout manager for UI elements. The layout is called TableLayout. You can arrange the elements in the cells of the virtual table, and customize each cell. In general, it is quite convenient, and sometimes it turns out to do what it is difficult to do with pens in unity3d.

I packed all the pictures in the game into one textural satin - 1024 * 1024. Part of the place in the atlas is still free - this is nice. This, by the way, is one of the libgdx bonuses (and generally low-level engines) - you can precisely control what resources take up how much space. Unity3d itself packs pictures into atlases, but I didn’t fully understand how she does it, and most importantly, how to see the final result, how many atlases and how big it was.

Sounds and music. We don't have them. A woman with a cart - a mare is easier :)

Text resources - dictionaries, localization. Localization - json. Json is generally a great format if the data size is not too large.
Dictionaries - plain text. As someone may have noted above, we have two identical dictionaries for each language, but sorted in different ways. You can sort, of course, when you start the application - but it is better to sacrifice several hundred kilobytes of application size than with brakes during launch.

Fonts I used TrueType, ttf. Libgdx has a library for working with them, and it works well. Memory such fonts eat more, of course, than just texture, but the result is much better visually.

What I want to say. I wrote the version on Unity3d about a month. Rewrote in three days on libgdx. The comparison is not fair, because the assets have already been prepared, and the main part of the logic has been written. But according to my feelings, I would still need less time on libgdx than on Unity3d.

Several factors played a role. The first is that I know libgdx well, and not very well, Unity3d. Secondly - the idea of ​​the game and everything I needed, I had. The main result. And it’s like this - instead of 16 megabytes of braking APK (I’ve cut Android x86 support in Unity3d to achieve this size, otherwise I’ll get 20+) —I got an APK of 8 megabytes, and a quick one (stable 60 FPS with fullscreen translucent backgrounds). Plus the ability to easily interact with android-code. Minus - porting to ios will be more difficult, especially in light of the latest news about libgdx. But porting to ios is not clear when it will be, and whether it will be at all, and a stable android version is needed now.

For myself, I made a conclusion - for my projects I will use libgdx, and develop my engine, built on top of it. This will allow me not to shudder when Unity3d is updated to the next version, and not to think about how the build on Android will now work, whether the application will slow down. On the other hand, I will periodically feel for the next version of Unity3d - maybe the situation will improve, who knows. In general, it seems to me that Unity3d is going more towards desktop development, and therefore, they don’t really care about performance on mobile devices.

Monetization

The first version is fully functional and free, there are no additional features that can be bought for money. But there is an advertisement - a banner in the playing field below, and a full screen at the end of the game. In the future, we plan to introduce some bonuses that can be purchased for in-app - add a letter, change the letter, etc. More have not thought about it. First you need to bring it to mind (dictionary and other game modes), and then you can think about monetization.

Plans for updates

Mass plans. We want to add a user dictionary. I want to add a game over the network (I plan to write a server on Netty, I have some experience). Add achivki. Add new languages. There are a lot of ideas, but there is little time :) But a user dictionary will definitely be included in the nearest update - this is a necessary feature.

Results

This game was the second one I wrote, and which I myself enjoy playing. If you ask, which is the first - it is not mine, freelancing, and it has not yet come out. And it seems to me that this is the right way - to write games that you play with pleasure yourself. And to write them, such games, you need to be happy :)

PS If there are any nuances on the issues of game logic or libgdx - write in the comments. I understand that I cannot cover the whole topic, and could miss something, so I will be happy to answer any questions.