Author Topic: Object-oriented design with Simon  (Read 22556 times)

0 Members and 2 Guests are viewing this topic.

Online Simon

  • Administrator
  • Posts: 3950
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #30 on: April 26, 2020, 02:14:44 AM »
Covariance, Part 2: C++ hunch, then link

How to enjoy covariant return types in C++, but at the same time avoid returning raw pointers Animal* and instead return std::unique_ptr<Animal>? (See end of previous post for an example and a more elaborate statement of this problem.)

Language rule: The naive approach is not allowed. You cannot override std::unique_ptr<Animal> Animal::clone() using the different return type, e.g., std::unique_ptr<Cat> Cat::clone(), because C++ allows covariant return types only for raw pointers. std::unique_ptr is a libaray type template, not a language feature.

My first hunch would have been: Instead of declaring clone() public and have it return the raw pointers Animal* or Cat*, we declare cloneRaw() protected virtual (and continue to return the raw pointers), overriding it normally in each subclass. Then, we declare a single public nonvirtual interface function in the base:

std::unique_ptr<Animal> Animal::clone()
    return std::unique_ptr<Animal>(cloneRaw());
// where cloneRaw() might return Cat*, seen here as Animal*

  • We still have to write return new Cat(...) in Cat's implementation of the protected cloneAsRaw(), even though modern C++ suggests that we do not write raw new anymore.
  • Should anybody want std::unique_ptr<Cat>, they're hosed, unless Cat offers its own nonvirtual std::unique_ptr<Cat> cloneAsCat() which cannot be enforced at design time of the base class.
While looking for expert advice on this, I found the blog post by Fluent C++ on the covariance/unique_ptr problem. My hunch is indeed one of the ideas presented that works for flat hierarchies, accepting the hackish need to provide the nonvirtual public interface in every subclass. I still haven't studied the blog post well enough to the point where I could re-state each of its arguments and solutions. Thus, instead of my ramblings, here is the

Link: How to Return a Smart Pointer AND Use Covariance, Fluent C++ blog post, 2017

-- Simon
« Last Edit: April 26, 2020, 02:51:31 AM by Simon »

Offline EricLang

  • Posts: 464
    • View Profile
Re: Object-oriented design with Simon
« Reply #31 on: April 27, 2020, 04:21:39 PM »
There is something about smart pointers in Game Coding Complete - 4th Edition.pdf which is a nice book to read anyway.
Probably there is a new edition already and I lost the link leading to the pdf.

Online Simon

  • Administrator
  • Posts: 3950
    • View Profile
    • Lix
Re: Object-oriented design with Simon
« Reply #32 on: June 28, 2020, 07:37:32 PM »

I'll explain the Lix level data structure: what the level contains after the level's text file has been parsed, but before we play the level. This is my first step to describe my triple dispatch problem.

Consider the Lix level Building Block Maze.

There are more than 40 yellow building blocks in this level. You'll find their graphics in ./images/geoo/sandstone/. When Lix wants to render this level, it too must load these graphics files.

Even though the level contains over 40 blocks, Lix only loads these 11 images.

Tiles and Occurrences. Look at the exit tile (archway with staircase). This is a single Tile. Building Block Maze contains two Occurrences of this single Tile, one in the top left and one in the top right.

A Tile is the result of a tile image loaded from disk. A Tile has a certain size, a mask, and knows whether it's terrain, steel, hatch, exit, ...

class Tile:
    Bitmap bitmap
    constructor(String filename):
        bitmap = expensive_load_from_disk(filename)

An Occurrrence, for the lack of a better word, is a usage of a Tile in a level. An Occurrence has a position, rotation, and knows whether it must be drawn normally or rather erase other terrain.

class Occurrence:
    const(Tile)* tile
    Point position
    int rotation
    bool erase

Reason. Loading a file from disk is expensive, and so is video memory. While it wouldn't be a problem loading 40 tiles instead of 11, it will be nasty when large levels contain 1,000 or 10,000 Occurrences, and we would have a disk load for each.

We want to load the same file only once, and have it in video memory only once. Since a Tile is immutable, i.e., it won't change anymore after it has been created successfully, many Occurrences can refer to the same Tile without risking bugs from sharing memory.

Problem with my naming. Tile and Occurrence are classes in Lix. I absolutely wanted to avoid naming either class Object, Instance or Class -- these names are already common OO parlance. Nonetheless, I'm unhappy. Colloquially, I often refer to an Occurrence as a Tile. This is a hint that the class names aren't optimal. Alternatives:
  • NeoLemmix calls my Tile a MetaTile and my Occurrence a Tile.
  • The traditional language of the Flyweight pattern calls my Tile the intrinsic state and my Occurrence the extrinsic state. Not short, not catchy, but standard.

Tile database. How to ensure that we really load every Tile at most once from disk? When a level parses its text file that calls for two exit Occurrences, the level shouldn't construct a Tile for that exit all by itself. Instead, we defer the responsibility of construction to a dedicated tile database, and, throughout the program, fetch the Tiles from that database. After all, tricky construction and bookeeping is at the heart of the problem, it makes sense to relieve everybody else from that worry.

The tile database treats the tile filenames as keys. When the Tile is wanted for the first time, the tile database loads the Tile from disk, caches it, and returns a reference to it. Every future time the same Tile is wanted, a reference to the already-cached Tile is returned.

The tile database, ideally, is its own class: Occasionally, it makes sense to delete and recreate the database, e.g., to unload all Tiles because their hardware bitmaps are are tied to a screen, and you want to change screen modes. It's also better for testing to avoid many global variables or singleton classes.

Still, even though you should design the tile database so that it's not a singleton, it still behaves much like global state, with the usual problems: You must either pass it around everywhere, or put it in your context object, or just make a single global database object because that's the least nasty solution.

Summary. Flyweight decomposes an object into two parts, the intrinsic immutable platonic ideal (Lix's Tile) and the extrinsic part that may vary every time we need the object (Lix's Occurrence). This is useful when the intrinsic part is expensive (Lix must load an image from disk), yet we want hundreds of instances. A key-value storage creates and remembers the intrinsics. The remainder of the program gets its intrinsics from there via keys (Lix's tile filenames).

Game programmers may invent all of this themselves. Then, years later, we read on the internet that this is a classic object-oriented pattern with a dedicated name, Flyweight. :lix-grin:

-- Simon
« Last Edit: June 28, 2020, 08:37:37 PM by Simon »

Offline namida

  • Administrator
  • Posts: 12425
    • View Profile
    • NeoLemmix Website
Re: Object-oriented design with Simon
« Reply #33 on: June 28, 2020, 08:44:58 PM »
Game programmers may invent all of this themselves. Then, years later, we game programmers read on the internet that this is a classic object-oriented pattern with a dedicated name, Flyweight. :lix-grin:

In NL's case, it seemed like a natural evolution of the older "graphic set" setup (which were themself stored as an object, which in turn had child objects for gadgets, terrains, as well as some metadata about colors etc) - the current code is based around a single global "Piece manager", but in its earliest form, the piece manager was really just a dynamic graphic set that loaded pieces from other graphic sets. It's slowly evolved over time to become less of a dynamic graphic set (though in a vague, "everyday" sense one could still call it that) and more of a true "piece manager".

Themes, which still exist, work much like the old graphic sets but with only the metadata (colors, lemming sprite specification, etc), not any terrains or gadgets. Those still exist, and even utilize some remnants of the old graphic set code. My understanding is that Lix doesn't allow customization of any of the things a NL theme file controls (other than by replacing the global graphic files), so wouldn't have an equivalent.
My Lemmings projects
2D Lemmings: NeoLemmix (engine) | Lemmings Plus Series (level packs) | Doomsday Lemmings (level pack)
3D Lemmings: Loap (engine) | L3DEdit (level / graphics editor) | L3DUtils (replay / etc utility) | Lemmings Plus 3D (level pack)