8 Puzzle for Linux

[Jonax]

Fellow pascal game developers!

I'm pleased to give a pre-view of yet a Linux game. Again it's from an old and tested concept with my own touch added.
The 8 puzzle. The smaller cousin of the more famous 15 puzzle. The added touch is the non international standard number systems.

( Unfortunately I don't speak either of Chinese, Thai, Ethiopian or Greek languages so I had to rely on internet search for getting those numerals. )

As usual the file is incredibly small and system requirements modest. In this case there's not even a timer function involved. Pure logic.
The game/puzzle runs well in virtual linux machines.
Hopefully the program behaves well on HighDPI settings.

There is probably more polishing to do, depending on feedback, but the game is fully playable already.

One missing point is the start position. Now always the same. Randomized start values is on the to do list. However it's not as simple as just placing the tiles at random. From what I read not all combinations are solvable.

I can also mention the puzzle may appear in some form in some future adventure style game..

Anyway.. enjoy the 8 puzzzle.. feedback is always welcome

:)

https://www.jonax.se/linux/8puzzle.php


https://www.jonax.se/enzip/8puzzle.gif

[SilverWarior]

This is much more known as sliding puzzle. https://en.wikipedia.org/wiki/Sliding_puzzle


Randomized start values is on the to do list. However it's not as simple as just placing the tiles at random. From what I read not all combinations are solvable.

As far as I know all starting configurations of sliding puzzle are solvable.

Sliding puzzles more often use images instead of numbers. So I suggest you add support for using images within your game.
In fact why not add ability for your program to be able to load one "final" image which is then split into 9 images (3x3 grid) where you then use first 8 images instead of the numbers.
Game logic stays the same so implementing this should not be to difficult.

Then to make more variety you could add bigger girds like 4x4, 5x5, or even add some non squared grids like 3x4, 4,5 etc. Basically any sized grid larger than 2x3 works.

[Jonax]

As far as I know all starting configurations of sliding puzzle are solvable.


True, unless the starting tiles are messed up. E.g. like here


https://www.jonax.se/pic/temp/Screenshot_20230410.png


I haven't done the math myself and I'm not going to try digging into that but from what I understand start postions like that really are unsolvable.


I made an updated version (0410) to demonstrate what I mean. Download the new version. Click the Mission Impossible button and you get the teal coloured background and a supposedly unsolvable start mode.


The normal solvable modes are still there of course.

[Jonax]

Sliding puzzles more often use images instead of numbers. So I suggest you add support for using images within your game.


Indeed images is a great idea which I'd love to implement. :)


However there are obstacles. Most important to obtain suitable images. Despite I like to dabble in drawing and occasionally show some attempts, making visually pleasing art is not my forte.


At some point it might be helpful to cooperate with a professional illustrator but that's expensive and not on the radar. I'm afraid you guys will have to make do with my home made image stuff for now.


The second obstacle is the High DPI support. No doubt solvable but will complicate the illustration situation. Actually I will have to start thinking about that for the next project. Hint: think ASCII art :o. I guess SVG is an option but I have no experience there.

[SilverWarior]

Most important to obtain suitable images. Despite I like to dabble in drawing and occasionally show some attempts, making visually pleasing art is not my forte.

The thing about sliding puzzle is that you can easily take any image or photo that doesn't have to many things on it and slice it into multiple images that then represent the movable pieces and thus generate puzzle from such image. Sure you could use pretty much any image but sliding puzzles made from images that have lots of little details on them can be very hard.
You can check one of such examples on next website: https://www.artbylogic.com/puzzles/imgSlider/imageShuffle.htm


The second obstacle is the High DPI support. No doubt solvable but will complicate the illustration situation.

If you go the route of using images then you don't even need to worry about High DPI awareness. Why? High DPI awareness is what is needed for your application to render fonts properly taking into account system scaling settings since in reality fonts are actually rendered by the operating system through the use of a specific API's. But when dealing with images you have complete control yourself.
So all you need is for your source images to be in high enough resolution so they wont have to be stretched when shown on monitors with high resolution. As for showing suuch high resolution images on low resolution monitors. Well it is far easier to shrink large image down without loosing to much noticeable detail (take a look at all those thumbnails of your images that OS made for quickly browsing your image folders).


Actually I will have to start thinking about that for the next project. Hint: think ASCII art :o. I guess SVG is an option but I have no experience there.

If you go for ASCI art by using text based components like TMemo for instance the most important function for you might be TextWidth which returns width of specific text in pixels so you could size up your component so that it can store whole lines: https://www.freepascal.org/docs-html/rtl/graph/textwidth.html
I'm not sure if FreePascal version takes into account DPI scalling but I know that Delphi version does since it is thigtly contectged into a specific canvas so it knows which DPI scalling has been used for that specific canvas: https://docwiki.embarcadero.com/Libraries/Alexandria/en/Vcl.Graphics.TCustomCanvas.TextWidth
Just don't forget that you need to use monospaced fonts for ASCI art to work properly ;)

And if you decide to go with images you may want to learn about Bitmap fonts: https://en.wikipedia.org/wiki/Computer_font
Bitmap fonts or sometimes also referred as BitFonts are commonly used in games. Most often the bitmap font is just a black and white image where you have white characters on a black background.
Why white characters on black background? Because then you can also use such image directly as bitmask with which you can then control what part of another image is rendered and what skipped (area of white pixels is rendered while area of black pixels is skipped).
Yes bitmap fonts usually also contain characters drawn in different sizes so you can reduce the amount if shrinking or stretching of such font images in order to represent different sized characters.

Yes using vector graphics would make scaling most easy and smooth on any resolution but as far as I know FreePascal does not support vector graphics out of the box so you would have to find suitable 3rd part library to add such support to your application. Here you may encounter a problem because some of the available libraries may be limited to only specific platforms.
Not to mention that unless they are using extended CPU features or GPU features they could be quite slow. Sure if you have few vector based images your probably won't notice. But when you have several hundred of such images (one for each font character) the performance impact can be quite noticeable.
Do you know that modern fonts which are also known as TrueType fonts /at least on windows) are actually vector based fonts? You can check FontForge which is an open sourced font making/editing program to easily see how existing fonts are made: https://fontforge.org/en-US/ You might be surprised of how many details certain fonts can have.

[SilverWarior]

True, unless the starting tiles are messed up. E.g. like here

I stand corrected. Not all puzzles are solvable. I have just tested yours with several online solvers ;D None of them managed to solve it :D
I was never any good at solving these myself. Perhaps I might go and check how computers are trying to solve such puzzles and learn just as how I learned how to solve Sudoku puzzles ;)

[Jonax]

Perhaps I might go and check how computers are trying to solve such puzzles and learn just as how I learned how to solve Sudoku puzzles ;)

Inded it would be interesting to see how computers tackle problems like this. I guess for small puzzles like 3x3 brute force could do it, or some clever algorithm. Wouldn't be surprised if those already exist somewhere. I also assume this could be a good start for the upcoming AIs. New AI:s or students of AI probably get these puzzles as one of their first assignments. But I'm on thin ice here and I also have no intention to try to make a program for solving the puzzle.


What I do know for certain is that a friend's class at a local university once got the assignmet to program a 15-puzzle in pascal. That was a long time ago so he had to do the programming on paper at home and then try it out on the univerity computer when access was available. I never saw his result but I recall he was pretty proud about it.


Meanwhile replying to your other post will have to wait. Right now I'm struggling with the randomizing thingie. Hopefully something can be presented any week now.

[SilverWarior]

I guess for small puzzles like 3x3 brute force could do it, or some clever algorithm.

I doubt brute force approach would be very effective here. Why? To many chances to end up repeating same sets of moves within a loop which could then end up in endless cycle.


Wouldn't be surprised if those already exist somewhere.

Of course they do exist. One of the most common mentioned algorithm for solving Sliding puzzles is Iterative deepening A* algorithm: https://en.wikipedia.org/wiki/Iterative_deepening_A*

[Jonax]

Update:


Progress quicker than anticipated.
Random but solvable start mode now added (version 0413). Foreign numbers still available.
It seems to work as intended, but one never knows what bugs dwell in the dark corners of the code.
https://www.jonax.se/pic/temp/8Puzzle0413.png


Thanks for valuable feedback @silverwarior :)


No plans to use iterative deepening algorithms for this project.
Got to start tackling the graphics /ascii art situation first.
That will be a task for next mini-game project . Which hasn't started yet.

Now time to enjoy some well deserved beer and cheese :)

[Jonax]

Update: it turned out the lightweight desktop environment LXQT doesn't come with Thai or Ethiopian fonts installed. I assume it's the same for the Xfce. I'm sure there are ways to install desired fonts there but I have no such experience. I'm afraid I have to say the 8Puzzle works best on KDE or Gnome.


Haven't yet started with the ascii art project and haven't digested all the suggestions from SilverWarior, but I totally agree about the monospaced fonts. Very useful. :)

[Jonax]

Update:

New mini-game project is started with dual approach.
Background decoration as (huge) bitmap file. Currently linux allows 300 % scaling for the happy owners of huge monitors. So the image better be big enough to handle that.

In the new project the executable increases from previously ~3 MB to ~11 MB. Still reasonable but there may also be a gziped version for download.
What do you guys say? downloading 11 MB is no big deal nowadays? Compressing the file may be overkill?

Then for this project there is also the scalable vector graphics approach.
I try a home-made version using a series of

image.canvas.line(x1,y1,x2,y2);

commands.

The current result is shown below


https://jonax.se/pic/temp/Screenshot_20230518.png

(image may be removed from the server at some later time)

Quite blocky but it scales decently and I start to like it.
Might even keep it. We will see. The ascii-art will have to wait.

The actual game?

Can you guess the theme from the presented "art"?

As often it's a variation of an old and well known concept, with some Jonax touch added.

Hopefully it can be presented any week now. At least if I make do with the above "art" and solve a few remaining bullet points.

[SilverWarior]

What do you guys say? downloading 11 MB is no big deal nowadays? Compressing the file may be overkill?

11 MB is no big deal today. Especially if you take into account that may web-pages can exceed 5 MB od downloadable data per page.
As for tying to reduce size of your executable that has increased due to including a large image in it. You can do a lot by using appropriate image format. For instance:
If your image has low number of colors then using PNG image format would reduce the data size the most due the way PNG image compression works.
If your image has lots of colors like in a photo then using JPEG might be better idea since JPEG compression is developed to better handle this kind of images.
You should avoid storing images in plain BMP format since BMP offers no compression.



I try a home-made version using a series of

image.canvas.line(x1,y1,x2,y2);

You should check TCanvas.Polyline (https://lazarus-ccr.sourceforge.io/docs/lcl/graphics/tcanvas.polyline.html) which allows you to draw a line across a an array of points. It will probably make your life a bit easier ;)
And of you want less "linear" results ;D you may also want to check TCanvas.PolyBezier (https://lazarus-ccr.sourceforge.io/docs/lcl/graphics/tcanvas.polybezier.html) which allows drawing of nice curved lines.

[Jonax]

Thanks for input and suggestions :). I'll probably skip the zipping. Indeed the PNG and JPG formats are great. I think in this case I had some problem making it work with PNG, while a BMP-file behaved well albeit being huge. Anyway. First priority is to create something executable and playable at all.

I'll have a look at the polyline and bezier suggestions.
Indeed my approach while getting the job done started to get cumbersome, as more points were added :o. In fact I spent 100 lines of code just to make that image. A polyline with array could no doubt simplify things. And more curvy lines can add some allure.

There's still some polishing and adding of functionality to do so nothing can be presented yet. Hopefully a new thread can be started for the new project in the coming week(s). ;D

[SilverWarior]

In fact I spent 100 lines of code just to make that image.

100 lines of code for that ???
What are you doing to need 100 lines for that. I can draw that using 33 lines of code ;)
I hope you are not setting brush properties (color, thickness, brus style) and starting position for each line segment.

How I draw teh same image as you did

procedure TForm1.DrawNormal;begin
//Fill background
Image1.Canvas.Brush.Style := TBrushStyle.bsSolid;
Image1.Canvas.Brush.Color := clBlack;
Image1.Canvas.FillRect(Image1.Canvas.ClipRect);


//Set pen properties
Image1.Canvas.Pen.Style := TPenStyle.psSolid;
Image1.Canvas.Pen.Color := clWhite;
Image1.Canvas.Pen.Width := 2;


//Move to starting position
Image1.Canvas.MoveTo(16,144);


//Draw lines to next points
Image1.Canvas.LineTo(16,128);
Image1.Canvas.LineTo(32,128);
Image1.Canvas.LineTo(16,80);
Image1.Canvas.LineTo(16,32);
Image1.Canvas.LineTo(32,16);
Image1.Canvas.LineTo(48,16);
Image1.Canvas.LineTo(32,32);
Image1.Canvas.LineTo(80,32);
Image1.Canvas.LineTo(128,48);
Image1.Canvas.LineTo(128,80);
Image1.Canvas.LineTo(80,64);
Image1.Canvas.LineTo(80,80);
Image1.Canvas.LineTo(128,96);
Image1.Canvas.LineTo(128,128);
Image1.Canvas.LineTo(144,128);
Image1.Canvas.LineTo(144,144);
Image1.Canvas.LineTo(16,144);
end;

After looking more closely at positional values I noticed that all of them are multiple of 16 so I'm guessing 16 is your scalability factor for this image.So I then wrote a code that can draw your image using different scalability factors and thus allow scaling


procedure TForm1.DrawScaled(ScaleSize: Integer);
begin
//Fill background
Image2.Canvas.Brush.Style := TBrushStyle.bsSolid;
Image2.Canvas.Brush.Color := clBlack;
Image2.Canvas.FillRect(Image1.Canvas.ClipRect);


//Set pen properties
Image2.Canvas.Pen.Style := TPenStyle.psSolid;
Image2.Canvas.Pen.Color := clWhite;
Image2.Canvas.Pen.Width := 2;


//Move to starting position
Image2.Canvas.MoveTo(1*ScaleSize,9*ScaleSize);


//Draw lines to next points
Image2.Canvas.LineTo(1*ScaleSize,8*ScaleSize);
Image2.Canvas.LineTo(2*ScaleSize,8*ScaleSize);
Image2.Canvas.LineTo(1*ScaleSize,5*ScaleSize);
Image2.Canvas.LineTo(1*ScaleSize,2*ScaleSize);
Image2.Canvas.LineTo(2*ScaleSize,1*ScaleSize);
Image2.Canvas.LineTo(3*ScaleSize,1*ScaleSize);
Image2.Canvas.LineTo(2*ScaleSize,2*ScaleSize);
Image2.Canvas.LineTo(5*ScaleSize,2*ScaleSize);
Image2.Canvas.LineTo(8*ScaleSize,3*ScaleSize);
Image2.Canvas.LineTo(8*ScaleSize,5*ScaleSize);
Image2.Canvas.LineTo(5*ScaleSize,4*ScaleSize);
Image2.Canvas.LineTo(5*ScaleSize,5*ScaleSize);
Image2.Canvas.LineTo(8*ScaleSize,6*ScaleSize);
Image2.Canvas.LineTo(8*ScaleSize,8*ScaleSize);
Image2.Canvas.LineTo(9*ScaleSize,8*ScaleSize);
Image2.Canvas.LineTo(9*ScaleSize,9*ScaleSize);
Image2.Canvas.LineTo(1*ScaleSize,9*ScaleSize);
end;

PS: If you try to directly compile my code you may have to make slight changes where I set-up brush and pen style. Modern Delphi versions define many constants like Brush Style as sets instead of series of constants as it have been done in older versions of Delphi and is probably done in FPC. This then require slightly different code.

[Jonax]

No multiple setting of properties, just the setting of four coordinates per line segment and liberal use of newlines and comments.


Obviously your approach is more compact and easier to use. I'm pleased to confirm the Canvas.LineTo(x,y) command also works for Lazarus. So LineTo it will be.


Indeed that image has scalability factor 16.