Games: Add a 2048 game

8 files changed, 522 insertions, 0 deletions

diff --git a/Base/res/apps/2048.af b/Base/res/apps/2048.af
new file mode 100644
index 0000000000..e8ea8ed053
--- /dev/null
+++ b/Base/res/apps/2048.af
@@ -0,0 +1,8 @@
+[App]
+Name=2048
+Executable=/bin/2048
+Category=Games
+
+[Icons]
+16x16=/res/icons/16x16/app-2048.png
+32x32=/res/icons/32x32/app-2048.png
diff --git a/Base/res/icons/16x16/app-2048.png b/Base/res/icons/16x16/app-2048.png
new file mode 100644
index 0000000000..bc469db96c
--- /dev/null
+++ b/Base/res/icons/16x16/app-2048.png
diff --git a/Base/res/icons/32x32/app-2048.png b/Base/res/icons/32x32/app-2048.png
new file mode 100644
index 0000000000..8b6c27343f
--- /dev/null
+++ b/Base/res/icons/32x32/app-2048.png
diff --git a/Games/2048/2048.cpp b/Games/2048/2048.cpp
new file mode 100644
index 0000000000..e35b4c4b15
--- /dev/null
+++ b/Games/2048/2048.cpp
@@ -0,0 +1,351 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "2048.h"
+#include <LibCore/ConfigFile.h>
+#include <LibGUI/FontDatabase.h>
+#include <LibGUI/MessageBox.h>
+#include <LibGUI/Painter.h>
+#include <LibGfx/Bitmap.h>
+#include <LibGfx/Font.h>
+#include <LibGfx/Palette.h>
+#include <stdlib.h>
+#include <time.h>
+
+TwentyFortyEightGame::TwentyFortyEightGame()
+{
+    set_font(GUI::FontDatabase::the().get_by_name("Liza Regular"));
+    srand(time(nullptr));
+    reset();
+}
+
+TwentyFortyEightGame::~TwentyFortyEightGame()
+{
+}
+
+template<typename Board>
+void TwentyFortyEightGame::add_tile(Board& board, int max_tile_value)
+{
+    int row;
+    int column;
+    do {
+        row = rand() % m_rows;
+        column = rand() % m_columns;
+    } while (board[row][column] != 0);
+
+    int value = rand() % max_tile_value;
+    value = round_up_to_power_of_two(value, max_tile_value);
+    board[row][column] = max(2, value);
+}
+
+void TwentyFortyEightGame::reset()
+{
+    auto initial_state = [&]() -> State {
+        State state;
+        state.board.resize(m_columns);
+        auto& board = state.board;
+        for (auto& row : board) {
+            row.resize(m_rows);
+            for (auto& j : row)
+                j = 0;
+        }
+
+        add_tile(state.board, m_starting_tile);
+        add_tile(state.board, m_starting_tile);
+
+        return state;
+    };
+
+    m_states.clear();
+    m_states.append(initial_state());
+
+    m_states.last().score_text = String::format("Score: %d", score());
+
+    update();
+}
+
+Gfx::IntRect TwentyFortyEightGame::score_rect() const
+{
+    int score_width = font().width(m_states.last().score_text);
+    return { 0, 2, score_width, font().glyph_height() };
+}
+
+static Vector<Vector<u32>> transpose(const Vector<Vector<u32>>& board)
+{
+    Vector<Vector<u32>> new_board;
+    auto result_row_count = board[0].size();
+    auto result_column_count = board.size();
+
+    new_board.resize(result_row_count);
+
+    for (size_t i = 0; i < board.size(); ++i) {
+        auto& row = new_board[i];
+        row.clear_with_capacity();
+        row.ensure_capacity(result_column_count);
+        for (auto& entry : board) {
+            row.append(entry[i]);
+        }
+    }
+
+    return new_board;
+}
+
+static Vector<Vector<u32>> reverse(const Vector<Vector<u32>>& board)
+{
+    auto new_board = board;
+    for (auto& row : new_board) {
+        for (size_t i = 0; i < row.size() / 2; ++i)
+            swap(row[i], row[row.size() - i - 1]);
+    }
+
+    return new_board;
+}
+
+static Vector<u32> slide_row(const Vector<u32>& row)
+{
+    if (row.size() < 2)
+        return row;
+
+    auto x = row[0];
+    auto y = row[1];
+
+    auto result = row;
+    result.take_first();
+
+    if (x == 0) {
+        result = slide_row(result);
+        result.append(0);
+        return result;
+    }
+
+    if (y == 0) {
+        result[0] = x;
+        result = slide_row(result);
+        result.append(0);
+        return result;
+    }
+
+    if (x == y) {
+        result.take_first();
+        result = slide_row(result);
+        result.append(0);
+        result.prepend(x + x);
+        return result;
+    }
+
+    result = slide_row(result);
+    result.prepend(x);
+    return result;
+}
+
+static Vector<Vector<u32>> slide_left(const Vector<Vector<u32>>& board)
+{
+    Vector<Vector<u32>> new_board;
+    for (auto& row : board)
+        new_board.append(slide_row(row));
+
+    return new_board;
+}
+
+static bool is_complete(const TwentyFortyEightGame::State& state)
+{
+    for (auto& row : state.board) {
+        if (row.contains_slow(2048))
+            return true;
+    }
+
+    return false;
+}
+
+static bool has_no_neighbors(const Span<const u32>& row)
+{
+    if (row.size() < 2)
+        return true;
+
+    auto x = row[0];
+    auto y = row[1];
+
+    if (x == y)
+        return false;
+
+    return has_no_neighbors(row.slice(1, row.size() - 1));
+};
+
+static bool is_stalled(const TwentyFortyEightGame::State& state)
+{
+    static auto stalled = [](auto& row) {
+        return !row.contains_slow(0) && has_no_neighbors(row.span());
+    };
+
+    for (auto& row : state.board)
+        if (!stalled(row))
+            return false;
+
+    for (auto& row : transpose(state.board))
+        if (!stalled(row))
+            return false;
+
+    return true;
+}
+
+void TwentyFortyEightGame::keydown_event(GUI::KeyEvent& event)
+{
+    auto& previous_state = m_states.last();
+    State new_state;
+    switch (event.key()) {
+    case KeyCode::Key_A:
+    case KeyCode::Key_Left:
+        new_state.board = transpose(slide_left(transpose(previous_state.board)));
+        break;
+    case KeyCode::Key_D:
+    case KeyCode::Key_Right:
+        new_state.board = transpose(reverse(slide_left(reverse(transpose(previous_state.board)))));
+        break;
+    case KeyCode::Key_W:
+    case KeyCode::Key_Up:
+        new_state.board = slide_left(previous_state.board);
+        break;
+    case KeyCode::Key_S:
+    case KeyCode::Key_Down:
+        new_state.board = reverse(slide_left(reverse(previous_state.board)));
+        break;
+    case KeyCode::Key_U:
+    case KeyCode::Key_Backspace:
+        if (m_states.size() > 1) {
+            m_states.take_last();
+            update();
+        } else {
+            return;
+        }
+    default:
+        return;
+    }
+
+    if (new_state.board != previous_state.board) {
+        add_tile(new_state.board, m_starting_tile * 2);
+        if (m_states.size() == 16)
+            m_states.take_first();
+        m_states.append(move(new_state));
+
+        m_states.last().score_text = String::format("Score: %d", score());
+
+        update();
+    }
+
+    if (is_complete(m_states.last())) {
+        // You won!
+        GUI::MessageBox::show(window(),
+            String::format("Score = %d", score()),
+            "You won!",
+            GUI::MessageBox::Type::Information);
+        return game_over();
+    }
+
+    if (is_stalled(m_states.last())) {
+        // Game over!
+        GUI::MessageBox::show(window(),
+            String::format("Score = %d", score()),
+            "You lost!",
+            GUI::MessageBox::Type::Information);
+        return game_over();
+    }
+}
+
+void TwentyFortyEightGame::paint_event(GUI::PaintEvent&)
+{
+    static auto color_for_entry = [&](u32 entry) -> Color {
+        constexpr static u8 blend_alpha = 128;
+        switch (entry) {
+        case 0:
+            return palette().base().lightened();
+        case 2:
+            return palette().base().blend(Color(Color::LightGray).with_alpha(blend_alpha));
+        case 4:
+            return palette().base().blend(Color(Color::WarmGray).with_alpha(blend_alpha));
+        case 8:
+            return palette().base().blend(Color(Color::MidMagenta).with_alpha(blend_alpha));
+        case 16:
+            return palette().base().blend(Color(Color::Magenta).with_alpha(blend_alpha));
+        case 32:
+            return palette().base().blend(Color(Color::Cyan).with_alpha(blend_alpha));
+        case 64:
+            return palette().base().blend(Color(Color::DarkCyan).with_alpha(blend_alpha));
+        case 128:
+            return palette().base().blend(Color(Color::MidBlue).with_alpha(blend_alpha));
+        case 256:
+            return palette().base().blend(Color(Color::Blue).with_alpha(blend_alpha));
+        case 512:
+            return palette().base().blend(Color(Color::DarkBlue).with_alpha(blend_alpha));
+        case 1024:
+            return palette().base().blend(Color(Color::Yellow).with_alpha(blend_alpha));
+        case 2048:
+            return palette().base().blend(Color(Color::Green).with_alpha(blend_alpha));
+        default:
+            ASSERT_NOT_REACHED();
+        }
+    };
+
+    GUI::Painter painter(*this);
+
+    painter.draw_text(score_rect(), m_states.last().score_text, font(), Gfx::TextAlignment::TopLeft, palette().color(ColorRole::BaseText));
+
+    painter.translate(0, font().glyph_height() + 2);
+
+    constexpr size_t column_padding = 2, row_padding = 2;
+    size_t column_offset = column_padding, row_offset = row_padding;
+    float column_size = (height() - font().glyph_height() - 2 - column_padding) / m_columns, row_size = (width() - 2 * row_padding) / m_rows;
+
+    for (auto column = 0; column < m_columns; ++column) {
+        for (auto row = 0; row < m_rows; ++row) {
+            auto rect = Gfx::IntRect(column_offset, row_offset, column_size - column_padding, row_size - row_padding);
+            painter.draw_rect(rect, Color::White);
+            auto entry = m_states.last().board[row][column];
+            painter.fill_rect(rect.shrunken(1, 1), color_for_entry(entry));
+            if (entry > 0)
+                painter.draw_text(rect, String::number(entry), font(), Gfx::TextAlignment::Center, palette().color(ColorRole::BaseText));
+
+            column_offset += column_size;
+        }
+        column_offset = column_padding;
+        row_offset += row_size;
+    }
+}
+
+void TwentyFortyEightGame::game_over()
+{
+    reset();
+}
+
+int TwentyFortyEightGame::score() const
+{
+    u32 score = 0;
+    for (auto& row : m_states.last().board) {
+        for (auto& element : row)
+            score = max(score, element);
+    }
+
+    return score;
+}
diff --git a/Games/2048/2048.h b/Games/2048/2048.h
new file mode 100644
index 0000000000..d2368cc121
--- /dev/null
+++ b/Games/2048/2048.h
@@ -0,0 +1,61 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/NonnullRefPtrVector.h>
+#include <LibGUI/Widget.h>
+
+class TwentyFortyEightGame final : public GUI::Widget {
+    C_OBJECT(TwentyFortyEightGame)
+public:
+    virtual ~TwentyFortyEightGame() override;
+
+    void reset();
+    int score() const;
+
+    struct State {
+        Vector<Vector<u32>> board;
+        String score_text;
+    };
+
+private:
+    TwentyFortyEightGame();
+    virtual void paint_event(GUI::PaintEvent&) override;
+    virtual void keydown_event(GUI::KeyEvent&) override;
+
+    void game_over();
+    Gfx::IntRect score_rect() const;
+
+    template<typename Board>
+    void add_tile(Board& board, int max_tile_value);
+
+    int m_rows { 4 };
+    int m_columns { 4 };
+    u32 m_starting_tile { 2 };
+
+    Vector<State, 16> m_states;
+};
diff --git a/Games/2048/CMakeLists.txt b/Games/2048/CMakeLists.txt
new file mode 100644
index 0000000000..54659c00ba
--- /dev/null
+++ b/Games/2048/CMakeLists.txt
@@ -0,0 +1,7 @@
+set(SOURCES
+    main.cpp
+    2048.cpp
+)
+
+serenity_bin(2048)
+target_link_libraries(2048 LibGUI)
diff --git a/Games/2048/main.cpp b/Games/2048/main.cpp
new file mode 100644
index 0000000000..085f397648
--- /dev/null
+++ b/Games/2048/main.cpp
@@ -0,0 +1,94 @@
+/*
+ * Copyright (c) 2020, the SerenityOS developers.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "2048.h"
+#include <LibGUI/AboutDialog.h>
+#include <LibGUI/Action.h>
+#include <LibGUI/Application.h>
+#include <LibGUI/BoxLayout.h>
+#include <LibGUI/Button.h>
+#include <LibGUI/Menu.h>
+#include <LibGUI/MenuBar.h>
+#include <LibGUI/Window.h>
+#include <stdio.h>
+
+int main(int argc, char** argv)
+{
+    if (pledge("stdio rpath wpath cpath shared_buffer accept cpath unix fattr", nullptr) < 0) {
+        perror("pledge");
+        return 1;
+    }
+
+    auto app = GUI::Application::construct(argc, argv);
+
+    auto window = GUI::Window::construct();
+
+    if (pledge("stdio rpath shared_buffer wpath accept", nullptr) < 0) {
+        perror("pledge");
+        return 1;
+    }
+
+    if (unveil("/res", "r") < 0) {
+        perror("unveil");
+        return 1;
+    }
+
+    if (unveil(nullptr, nullptr) < 0) {
+        perror("unveil");
+        return 1;
+    }
+
+    window->set_double_buffering_enabled(false);
+    window->set_title("2048");
+    window->set_rect(100, 100, 324, 336);
+
+    auto& game = window->set_main_widget<TwentyFortyEightGame>();
+    game.set_fill_with_background_color(true);
+
+    auto menubar = GUI::MenuBar::construct();
+
+    auto& app_menu = menubar->add_menu("2048");
+
+    app_menu.add_action(GUI::Action::create("New game", { Mod_None, Key_F2 }, [&](auto&) {
+        game.reset();
+    }));
+    app_menu.add_action(GUI::CommonActions::make_quit_action([](auto&) {
+        GUI::Application::the()->quit();
+    }));
+
+    auto& help_menu = menubar->add_menu("Help");
+    help_menu.add_action(GUI::Action::create("About", [&](auto&) {
+        GUI::AboutDialog::show("2048", Gfx::Bitmap::load_from_file("/res/icons/32x32/app-2048.png"), window);
+    }));
+
+    app->set_menubar(move(menubar));
+
+    window->show();
+
+    window->set_icon(Gfx::Bitmap::load_from_file("/res/icons/16x16/app-2048.png"));
+
+    return app->exec();
+}
diff --git a/Games/CMakeLists.txt b/Games/CMakeLists.txt
index ea6349a6da..96e33c0b03 100644
--- a/Games/CMakeLists.txt
+++ b/Games/CMakeLists.txt
@@ -1,3 +1,4 @@
+add_subdirectory(2048)
 add_subdirectory(Minesweeper)
 add_subdirectory(Snake)
 add_subdirectory(Solitaire)