My first big OpenProcessing project, planned out beforehand and then evolved over a series of days, Rune Recognition was built as a trainer for the game OrbusVR. In the game, to cast magic you must "draw" certain spells in the air. There is a small margin of error to encourage physical skill and practice in drawing these quickly and accurately, a system I really admired in game.
The way it detects which spell you're drawing, and how accurately, really interested me so I set about building a similar system. It needed to have a few set features:
- Check a large number of spells and accurately tell you which one was cast if successful
- Allow you to draw the symbols any size and anywhere on screen
- Variable margin of error to allow someone to start off easily and increase difficulty
- Easy way to add more spells for it to recognize.
I knew early on that the system I had in mind, checking the points of the line drawn against known points of a rune, would be very computationally intensive. This meant I would need a way to simplify it as much as possible without losing detail. A straight line should be simplified to just two points, but I didn't want curves to be distorted. This lead me to a library called Simplify.js which had an excellent function for taking a line made up of a series of points and dynamically simplifying it while preserving important features. It had a parameter that controlled how much to simplify the line, so I was able to find a balance between keeping as much detail as possible while reducing computational load.
My first attempt had all of the runes defined as a series of points in an array. I created a small helper function that allowed me to draw the rune on screen, have it simplified to a series of points so I could save that in the program. This meant I didn't have to define each point by coordinates and could just draw it instead.
Each rune was then processed so each point was instead defined in terms of the first one (i.e [5, 7] was a point 5 units to the right and 7 units beneath the first). This made it easy to draw anywhere on screen since I simply set the first point to where the mouse started drawing and everything else was drawn in relation to it. I also included a function that would check the scale of the lines being drawn by the mouse and then scale the relative points accordingly. This meant that I had the second and fourth point completed, and a good base to work on actually checking whether or not a rune matched one of those stored.
I then wrote a function that checked how many of the vertices making up the rune had a drawn vertex within a certain distance of them, and as long as this was above a given tolerance (80% by default), it would consider it that rune. However, this was run for each rune, and if there was another rune also above the threshold but with an even higher percentage, then it became the newly assumed result.
This ticked off the first and third points, since I now had a way to accurately identify runes, and could adjust this tolerance value. The first attempt is seen below:
(To use it start drawing, and then follow one of the guides as they appear. Press "Space" when done to check it against the list of runes.)
This has a few problems however. The biggest being:
- You must start from the same starting point (i.e if the stored rune starts from the top, and other points are drawn beneath it, when drawing you must also start from the top)
- Once you had filled all of the points, as long as you didn't change the scale, extra drawing is ignored (e.g. draw the vertical arrow of Ice Lance, and then draw a circle to the side of it, and this will still be accepted)
- It shows the guides for all runes all the time, even those you are obviously not drawing
The next implementation sought to solve the first and second points together in its new implementation, and the last point I could add extra code for.
This second version, instead of basing the origin on the first point, it's based on the centre of mass (COM) of the drawn rune and the Node Map (saved rune). This has a number of advantages, namely it solves the problem of forcing you to start at the first point, since the COM evolves over time as you draw it but should be the same at the end no matter how you started drawing it. It has the same scaling code, though much refactoring took place between versions 1 and 2 to seperate concerns. This also solves the second point almost accidentally, since any superflous drawing is likely (unless its directly on it) to change the COM sufficiently to discard it as a possible rune.
The third point I had mixed success solving. I added a system whereby as you're drawing it, it runs the "checking" algorithm against it with a lower threshold to try and figure out which rune you are drawing and show you only the guide for that one. However, this does mean that for some of them, the guide does not appear until the rune is almost complete or if it does appear it's in the wrong place since the COM isn't finalised yet, and is therefore not particularly useful. The version based on Centre of Mass:
It is this problem of guides showuing wrongly that led me to make the third and final version, but looking at them now I think this implementation is actually not only less computationally efficient but also marginally less effective. It was interesting to do none the less, even if I think that the COM version ends up running the most smoothly and with the best accuracy. This third version (Cycle) worked by cycling through all of the points of all of the runes (hence running slightly more slowly), to try and figure out which point you started with. It does what COM did and runs the algorithm to figure out which of the possible starting points leads to the highest accuracy as you're drawing it, but since it now knows which point you're drawing relative to the guide stays still. This makes is easier to figure out where all lines need to be in relation to each other when drawing.
Cycle Version:
In conclusion it was a great project that was not only useful for actually learning all of the runes, but looking at how various implementations could solve it to varying degrees. Perhaps my favourite moment of the project was discovering a "shortcut" that actually worked in game. No small amount of effort was put into the game by the community to figure out the most efficient drawing that would still fufill all of the criteria of a given rune so it could be cast more quickly, and while using and testing this program I came across a shortcut that tricked it into thinking a given rune had been cast. I then tried this out in the game and it worked as well. By no means groundbreaking, but enough to know that the actual implementation in the game had many features similar to what I worked on here.
Comments