Architecture:Map Module: Difference between revisions

Latest revision as of 19:27, 17 April 2009

The map module is responsible for presenting the game world to the player. It is separate from the actual state of most game world elements, which are part of the RPG Module.

Map Objects and Shapes

On the outside, Adonthell is a 2D game, where the world consists entirely of 2D sprites as provided by the Gfx Module. Internally, for the purpose of collision detection, the extend of a sprite is represented by a simple 3D model, called its shape. The combination of sprite and shape are hereafter referred to as placeables'. They are persisted using the placeable format. The coordinate system used by shapes is as follows:

The camera position is fixed and provides for a top-down view on the map. It follows that the X axis in 3D space runs from west to east, the Y axis from north to south and the Z axis from bottom to top. Due to the top-down view, there is no visual distinction between Y and Z axis. It is not possible to view the sides of an object, only its front and top part. (Note that the image above diverts from that view for clarity.)

The map itself is assembled from placeables, which are stored in an octree-like structure that keeps track of their position. It also allows fast object retrieval for the purpose of collision detection or rendering of a scene. Usually, one placeable instance will be placed on the map multiple times, meaning that all these objects will share the same sprite and thus have the exact same state. This is fine for general scenery and objects that serve no particular purpose in the game itself. But there are also objects that need to be referenced by game scripts or objects that really need to have an individual state (doors or characters for example). The following figure shows how this is made possible by the underlying data structures:

Anonymous objects can be place multiple times on the map, but will share the same underlying placeable. Shared objects are placed on the map only once, but all of them still share the same placeable. Finally, unique objects are placed on the map only once and every one is backed by a distinct placeable instance. A placeable itself can either be a static scenery object, a moving creature or an item that can be picked up.

Collision Detection

The collision detection is implemented using the swept sphere algorithm described in [1]. Details regarding the algorithm can be found there. What remains to be described here is the coordinate-transformation that needs to take place in order to map absolute (pixel-)coordinates of moveable map objects to the relative coordinates of the shapes we test for collision.

To be explained later ...

Maps and Views

One prominent component of the engine is the renderer. It produces the graphical representation of a scene, and that about 40 times per second. (A new scene – or internal engine state – is computed about 75 times per second, btw.)

More important than those numbers or the fact that drawing and update operations are disjunct is the implementation. As the heading suggests, a model-view-controller (MVC) architecture is used.

The part of the map being displayed is determined by so-called mapviews. A mapview can be of any size and can direct output to any surface. Multiple mapviews can be active at the same time, although at present they can’t show different maps, just different areas of the same map.

The question that remains is how a mapview knows what part of a map to display. For that purpose, each mapview may have a schedule script assigned (the controller), which is executed before rendering takes place. The script in turn can use the methods provided by the mapview class for all kinds of effects. Usually, it will want to center the view on a certain character, but it is not limited to this.

Character Schedules

Character schedules are basically the "AI" behind NPCs and creatures, as they dictate the actions performed by a character. As most actions occur in context of a specific location, schedules are part of the world module. Schedules themselves are implemented in two layers. A master schedule determines the action to take in a specific situation, whereas an actual worker schedule performs the action.

The idea behind this layered system is that the master schedule basically implements a characters personality. As such it is often unique for a character or (class of) creature. The actions themselves are implemented as generic worker schedules, so that they can be reused across different characters, customized only through their input parameters. As development of actual games for the engine progresses, a library of worker schedules should evolve that can be used to create varied and distinct character behavior.

Once a master schedule has been assigned to a character and activated, it will be automatically triggered when the character is updated for the next game cycle. It will determine the worker schedule to start and if started successfully, it will wait for the worker schedule to stop.

The worker schedule, on starting up will have to trigger some actions, then register callbacks that will notify the worker that the actions are completed. On completion, it can trigger new actions, register new callbacks and continue to remain active. At any time in this cycle, it can be paused (in which case it should suspend any activity unless woken up). Once a worker schedule has finished its task and stops, the manager schedule will switch to running mode again, where it will be triggered during the next game cycle. It can now determine the next worker schedule to run.

As an alternative (not present in the diagram), a worker schedule can queue its successor in the schedule system. Once it stops, the schedule system will automatically start the queued worker script instead of running the manager schedule.

Map Events

The engine itself implements only the rendering of the map. Everything else, like transitions between map areas (characters entering buildings for example), interaction with items or characters on the map (picking up, initiating dialogue) and interaction with the map itself (traps, falling down) are handled by Python scripts. To trigger these scripts, so called map events are implemented and registered with the Event system.

The following events were implemented in the v0.3 engine and will probably appear in v0.4 as well:

An enter event is triggered when a character enters a location (tile)

A leave event is triggered when a character leaves a location (tile)

An action event is triggered when the player interacts with characters or objects on the map

@@ Line 1: / Line 1: @@
-''The map module for v0.4 is still in active development, so the section below is incomplete and in part refers to the v0.3 map engine. However, chances are that a new implementation will work in a similar fashion. For more details regarding the ongoing development refer to the [[Tasks:Mapengine|Mapengine]] and [[Tasks:Mapview|Mapview]] tasks.''
+The map module is responsible for presenting the game world to the player. It is separate from the actual state of most game world elements, which are part of the [[Architecture:Rpg Module|RPG Module]].
 == Map Objects and Shapes ==
-On the outside, Adonthell is a 2D game, where the world consists entirely of 2D sprites as provided by the [[Architectire:Gfx Module|Gfx Module]]. These, together with position information, are hereafter referred to as ''map objects''. Internally, for the purpose of collision detection, the extend of map objects is represented by a simple 3D model, called its ''shape''. Object model data is [[Architecture:Base Module#Data Persistance|persisted]] into an [[Architecture:Map Object Format| XML file]]. The coordinate system used by shapes is as follows:
+[[Image:3d-space.png|right|frame|The coordinate System used by Adontell]]
-[[Image:3d-space.png|center|frame|The coordinate System used by Adontell]]
+On the outside, Adonthell is a 2D game, where the world consists entirely of 2D sprites as provided by the [[Architecture:Gfx Module#Sprites|Gfx Module]]. Internally, for the purpose of collision detection, the extend of a sprite is represented by a simple 3D model, called its ''shape''. The combination of sprite and shape are hereafter referred to as ''placeables'. They are [[Architecture:Base Module#Data Persistence|persisted]] using the [[Architecture:Map Object Format| placeable format]]. The coordinate system used by shapes is as follows:
 The camera position is fixed and provides for a top-down view on the map. It follows that the X axis in 3D space runs from west to east, the Y axis from north to south and the Z axis from bottom to top. Due to the top-down view, there is no visual distinction between Y and Z axis. It is not possible to view the sides of an object, only its front and top part. ''(Note that the image above diverts from that view for clarity.)''
-The map itself is assembled from map objects, not from the underlying shapes. It consists of a grid (currently using cells of 40 by 40 pixels), where the map objects can be placed. By default, the top-left corner of a map object (i.e. sprite) is aligned to the top-left corner of the cell it is placed on. To allow more flexibility in placement of map objects, an offset can be specified. However, for non-flat sprites (i.e. walls or characters), the sprite is offset by the height of its underlying shape.
+The map itself is assembled from placeables, which are stored in an octree-like structure that keeps track of their position. It also allows fast object retrieval for the purpose of collision detection or rendering of a scene. Usually, one placeable instance will be placed on the map multiple times, meaning that all these objects will share the same sprite and thus have the exact same state. This is fine for general scenery and objects that serve no particular purpose in the game itself. But there are also objects that need to be referenced by game scripts or objects that really need to have an individual state (doors or characters for example). The following figure shows how this is made possible by the underlying data structures:
-All cells occupied by a map object hold a reference to that object, but one of them is special. The cell that contains the bottom-right corner of the map object is called the ''base'' of that object. It is important during the rendering phase, when the grid is traversed from left to right and top to bottom. For each cell, only those objects are drawn (according to their z-order) for which this cell is their base.
+[[Image:Map-elements.png|center|frame|The elements a map is build of]]
-[[Image:Object-placement.png|center|frame|The placement of Map Objects]]
+Anonymous objects can be place multiple times on the map, but will share the same underlying placeable. Shared objects are placed on the map only once, but all of them still share the same placeable. Finally, unique objects are placed on the map only once and every one is backed by a distinct placeable instance. A placeable itself can either be a static scenery object, a moving creature or an item that can be picked up.
-The example above shows two flat sprites (i.e. ground tiles) placed on the map grid. The first is sitting on the ground, but it is offset and thus spans multiple cells. The cell containing its bottom-right part is its base (marked by a red border). The second tile is floating at an altitude of 70px, but only occupies a single cell. Due to the top-down point of view, impression of altitude can only be achieved through sprites that are drawn to give that impression. No 3D techniques like shading or projecting shadows are employed by the engine, as the shapes have little part in the actual rendering.
-Similar to static objects,  the position of moving entities, such as creatures or NPCs, is kept in terms of cell-coordinates, offset from the cells' corner and current altitude. As a shape does hold no reference to the map object it belongs to, it does have no knowledge of its absolute position in the world. All it knows is its size (represented by a bounding box) and a relative position to the sprite, as shown below:
-[[Image:Model-alignment.png|center|frame|Alignment of Map Objects and Object Models]]
-From all the above follows that the position of a map object on the screen (in pixels) is determined as follows
-  x_px = X-Coordinate * GRID_SIZE + X-Offset
-  y_px = Y-Coordinate * GRID_SIZE + Y-Offset - Altitude - Shape-Height
 == Collision Detection ==
-The collision detection is implemented using a swept sphere algorithm described in [http://www.peroxide.dk/papers/collision/collision.pdf]. Details regarding the algorithm can be found there. What remains to be described here is the coordinate-transformation that needs to take place in order to map absolute (pixel-)coordinates of moveable map objects to the relative coordinates of the shapes we test for collision.
+The collision detection is implemented using the swept sphere algorithm described in [http://www.peroxide.dk/papers/collision/collision.pdf]. Details regarding the algorithm can be found there. What remains to be described here is the coordinate-transformation that needs to take place in order to map absolute (pixel-)coordinates of moveable map objects to the relative coordinates of the shapes we test for collision.
 ''To be explained later ...''
@@ Line 42: / Line 31: @@
 The part of the map being displayed is determined by so-called mapviews. A mapview can be of any size and can direct output to any surface. Multiple mapviews can be active at the same time, although at present they can’t show different maps, just different areas of the same map.
-The question that remains is how a mapview knows what part of a map to display. For that purpose, each mapview may have a schedule script assigned (the controller), which is executed before rendering takes place. The script in turn can use the methods provided by the mapview class for all kinds of effects. Usually, it will want to center the view on a certain [[Characters:Contents|character]], but it is not limited to this.
+The question that remains is how a mapview knows what part of a map to display. For that purpose, each mapview may have a [[Scripting:Map View|schedule script]] assigned (the controller), which is executed before rendering takes place. The script in turn can use the methods provided by the mapview class for all kinds of effects. Usually, it will want to center the view on a certain [[Characters:Contents|character]], but it is not limited to this.
+== Character Schedules ==
+[[Image:Master_worker_concept.png|right|frame|Character Schedules]]
+Character schedules are basically the "AI" behind NPCs and creatures, as they dictate the actions performed by a character. As most actions occur in context of a specific location, schedules are part of the world module. Schedules themselves are implemented in two layers. A master schedule determines the action to take in a specific situation, whereas an actual worker schedule performs the action.
+The idea behind this layered system is that the master schedule basically implements a characters personality. As such it is often unique for a character or (class of) creature. The actions themselves are implemented as generic worker schedules, so that they can be reused across different characters, customized only through their  input parameters. As development of actual games for the engine progresses, a library of worker schedules should evolve that can be used to create varied and distinct character behavior.
+[[Image:Master_worker_transitions.png|left|frame|States and Transitions]]
+Once a master schedule has been assigned to a character and activated, it will be automatically triggered when the character is updated for the next game cycle. It will determine the worker schedule to start and if started successfully, it will wait for the worker schedule to stop.
+The worker schedule, on starting up will have to trigger some actions, then register callbacks that will notify the worker that the actions are completed. On completion, it can trigger new actions, register new callbacks and continue to remain active. At any time in this cycle, it can be paused (in which case it should suspend any activity unless woken up). Once a worker schedule has finished its task and stops, the manager schedule will switch to running mode again, where it will be triggered during the next game cycle. It can now determine the next worker schedule to run.
+As an alternative (not present in the diagram), a worker schedule can queue its successor in the schedule system. Once it stops, the schedule system will automatically start the queued worker script instead of running the manager schedule.
 == Map Events ==