Allow entities of any size

[seisatsu]

Yes.

[seisatsu]

We will need to allow entities to occupy multiple tiles. This will probably require some restructuring.

[pmer]

TL;DR:

• Pixel-mode cannot have the concept of tiles being occupied.
• Pixel-mode needs a new collision detection engine.
• Pixel-mode can trivially support arbitrarily small and large entities.

Details below.

---

Here are some of my thoughts. They cover a number of areas in the engine, and should make Driftwood capable of supporting small and large entities and more natural entity movement in pixel-based games.

Parts of our "occupying a tile" concept are specific to tile-mode and turn-mode movement styles where all entities are approximately the size of one tile. In pixel-mode, all entities bigger than a 1×1 square may occupy multiple tiles.

Collision detection between pairs of entities

To solve the problem of collision detection between entities in turn-based mode, we have assumed that since an entity will always be on one tile we can simply enforce a maximum of one entity per tile. This assumption breaks down with pixel-mode, as demonstrated in the following cases:

• At the point of origin for a visual specific effect, twenty 1x1 entities are created in different location above the same tile.
• A line of people march one after another in tight formation. If the people are exactly one tile tall, then most of the time each tile has two people on it.

As an aside, the term occupancy, which implies a fullness and inability to hold any more, is an inappropriate label for tiles while operating in pixel-mode. We can instead say an entity is above a tile, or some such.

Our entity collision algorithm should be modified to detect collisions between the bounding boxes of entities. In pixel-mode, we can do this without regard to the tiles that a pair of entities are standing on. But in tile-mode we also need to look at the tiles to assert that two entites are not moving onto the same tile at the same time.

This change will solve the graphical glitch we current suffer from where an entity A positioned at point (x0, y0) may appear above another entity B at (x0+1, y0) if A moves up and B moves left at the same time.

Collision detection between entities and tiles

AKA how do on_tile triggers work now?

We can reify tile-based triggers into their own top-level Python objects called "trigger boxes." Trigger boxes are pairs of a rectangle and a function to call when an entity enters said rectangle. Areas have a list of these boxes and collision detection is modified to also check for collisions between entities and trigger boxes. When a hit occurs, we run the trigger & save to not run it again until the entity leaves the box.

nowalk tiles can be manifested in a similar fashion.

Advantages

Why would we want to do all this? Here is what we would gain:

• Adds support for small and large entities in pixel-mode
• Complex interactions among several medium entities (size ≈ 1 tile) works better, even in tile-based and turn-based movement modes
• Driftwood becomes easier to add cool features to because we solve collision in a more general manner

Disadvantages

• Slower (although there are popular, well-documented algorithms for speeding this up)
• Still does not make large entities in tile-mode and turn-mode work... that needs other changes

[pmer]

The above is for pixel-mode.

@seisatsu Do we want to support large entities in tile-mode and turn-mode?

[seisatsu]

We definitely want to support large entities in all modes. I like the idea of letting a trigger occupy multiple tiles, and it should only require a few lines of code.

There are reasons that pixel mode does require the concept of tiles being occupied, though not generally for collision purposes (though we do allow an option for pixel mode entities to collide this way.) The entity does need to know what tiles it is on to respond to triggers, but you are right that entity collisions are irrelevant to tiles entirely.

All of these ideas look sane.

[pmer]

Is there an example of a game that allows pixel-mode entities to collide by tile?

[seisatsu]

We can have a tile mode player but a pixel mode projectile that collides with them. Though, this might still work just fine with entity-only collision. This option really might not be needed.

[pmer]

@seisatsu, I didn't realize that tile and pixel-mode entities could exist in the same world. (Also hinted by you at https://github.com/seisatsu/Driftwood/issues/9#issuecomment-294423734)

We will also need to separate out pixel-mode entities into two types:

• Those that can co-exist on a single tile with a tile or turn-based entity
• And those that cannot

Projectiles, particles, and anything else has some acceptable semantic of colliding with a player fall into the former, while characters fall into the latter.

[pmer]

TL;DR:

• A proposal for how to handle arbitrarily-sized entities in any/all movement modes, even in mixed modes
• No more "tile occupancy" concept
• Instead, use bounding boxes in turn, tile, and pixel-based movements

I tried pushing the bounding box idea through to its ultimate conclusion. Looks like it solves some problems.

---

I propose we depreciate tile occupancy and use bounding boxes for collisions for all entities. This allows a single logic flow that can handle a heterogeneous mixture of entities of all sizes and movement modes, even within the same area. Tile occupancy was always a special case of the more general bounding box anyway.

Bounding box all the things

Depreciates tile occupancy.

Terminology

An entity e on layer l is above the set of tiles on l that collide with e's bounding box.

An entity e is static if other entities are not allowed to enter e's bounding box.

Collision resolution between static and non-static entities probably involves destroying the non-static entity. (E.g., the player (static) picks up a gold coin (non-static) on the ground.)

---

Turn-based entities

When a turn-based entity e tries to move, a check is performed to determine whether relocating e's bounding box at the new destination would collide with any entities. If e is static and it will collide with another static entity, e does not move. Otherwise, e's bounding box and graphic are moved to the destination immediately. Collision resolution is run between e and all entities now collided with it.

The bounding box of a turn-based entity is an arbitrarily-sized rectangle.

Turn-based entities can move in arbitrarily-sized jumps in any direction.

Tile-based entities

When a tile-based entity e tries to move, a check is performed to determine whether relocating e's bounding box at the new destination would collide with any entities. If e is static and it will collide with another static entity, e does not move. Otherwise, e's bounding box is moved to the destination immediately. e's graphic is scheduled to animation to its new position over time. During this time, e is walking. After e finishes walking, collision resolution is run between e and all entities currently collided with it, which may be a different set of entities than was found before e started walking.

The bounding box of a tile-based entity is a rectangle whose width and height are multiples of the area's tile width and height.

Tile-based entities must make vertical moves of one tile height or horizontal moves of one tile width.

Solving the "foot-face problem"

If an entity e positioned at point (x₀, y₀) moves up and then an entity f at (x₀+1, y₀) moves left, e may appear on top of f, leading to what I call the foot-face problem: e's foot may appear on top of f's face.

We can solve this problem by producing a second, cosmetic bounding box for e the size of e's graphic whose position follows e's walk. Every frame a tile-based entity walks, it checks to see if its cosmetic bounding box is intersecting with any other cosmetic bounding box. If so, it waits and does not move for the current frame. Pixel-based entities collide with cosmetic bounding boxes as if there was an actual entity there.

Making tile-based entities more flexible

Tile-based entities suffer the following limitations:

• The bounding box of a tile-based entity is a rectangle whose width and height are multiples of the area's tile width and height.
• Tile-based entities must make vertical moves of one tile height or horizontal moves of one tile width.

Both of these may be lifted by generalizing the cosmetic bounding box's shape. Collision detection & resolution will need to be changed to realize the new shapes.

Pixel-based entities

When a pixel-based entity e tries to move, a check is performed to determine whether relocating e's bounding box to a location the maximum distance away (for the current frame) would collide with any entities. If e is static and it will collide with another static entity, e moves up to the edge of the closest static entity. e may try to move around static entities, per #92. Collision resolution is then run between e and all non-static entities overlapping e's bounding box.

The bounding box of a pixel-based entity is an arbitrarily-sized rectangle.

Pixel-based entities can move at arbitrary speeds in any direction.

---

Interactions with trigger boxes

on_tile and exit triggers have non-static bounding boxes while nowalk tiles have static bounding boxes. No additional logic is necessary.

---

Anchors

If a turn or tile-based entity e has a bounding box whose width is not a multiple of the area's tile width, then e's bounding box must be horizontally anchored to the left, center, or right of a tile. Etc for vertical anchoring.

As an extra feature, we can allow an entity e whose bounding box is vertically anchored left or right (but not center) to have a horizontal anchor offset measured in pixels that determines how far away from the side of a tile the bounding box begins. Etc for horizontal anchoring offset.

---

Advantages

• Handles arbitrarily-sized entities in any movement modes
• No special code for interactions between entities in different movement modes

Disadvantages

• Slower

[pmer]

Even though I say tile occupancy won't exist anymore, you can still query for the set of tiles an entity is above. This is useful for trigger code.

[pmer]

A better solution to the "face-foot problem" above is actually to just sort entities by their Y-position before drawing them.

[pmer]

As it exists today, Driftwood is a turn- and tile-based engine with some modifications to allow for pixel-based entities.

The above proposal changes it into a pixel-based engine with some modifications to allow turn- and tile-based entities.

Which kind of makes sense because small and large entities do kind of break a lot of the assumptions we've made in turn- and tile-based movement modes... Things which are much easier to think about in a pixel-based world.

[seisatsu]

I think we will almost completely redesign and rewrite entity.py at this rate. Making this many changes to the existing code will most likely spaghettify it, and all of this could probably benefit from a total redesign of the code structure. I may want to save this for beta.

[seisatsu]

I added a github project for this to our repository. We can break this up into pieces when we're getting to where we want to start tackling it.

[pmer]

I split this issue up into two pieces. The first can be for Beta-0.1.0.

[seisatsu]

May require fixing #138.