How can I create a world map like Mario 3's?

Question

I want to create a world map similar to the type that Mario 3 on NES uses

where Mario can walk between levels (nodes?) by pressing up, down, left and right on the controller, and Mario can only pass through a level when it has been cleared.

What I have so far is a list of level nodes:

std::vector<SLevelNode*> NodeList;

struct SLevelNode
{
    CVector2D Position;
    CVector2D Size;
    CVector2D Origin;

    int ID;
    int Type;

    SLevelNode* pNeighbourNode[4];
};

The level node contains stuff like position, the type of level node (ground level, water level, castle level and so on). It also contain a neighbor node array, which in my case is 4, since I want the player to, eventually, be able to walk from a level node in all four directions. A level node might only have two ways of travel though, left and right for example.

Besides the level node, I also have a path piece, which is a piece of road between the level nodes:

struct SPathPiece
{
    CVector2D Position;
    CVector2D Size;
    CVector2D Origin;

    int Type;

    float Rotation;
};

The type variable is either a horizontal piece, a curve piece, a bridge piece and so on.

So far my character can walk between the level nodes by dragging a 2D vector between them, that the player traverse with. I want, however, the player to start walking from a level node, walk through the road pieces (between the nodes) and end up at the goal level node. I'm not sure how to make the level nodes "know about" the road pieces that is placed between the start node and the goal node. Have a list of path pieces in each level node?

I have though about using A* and make a path finding map but it feels like it's over-complicates things.

I would like some help on how to achieve this.

Answer 1

I would adjust SPathPiece so that it knows about the nodes it connects.

struct SPathPiece
{
    CVector2D Position;
    CVector2D Size;
    CVector2D Origin;

    int Type;

    float Rotation;
    SLevelNode * ConnectedNodes
};

I would then hook up the nodes that the road connects. For the pawn to walk I would put in a basic FSM

• stateLeaveCurrentNode
• stateWalkPath
• stateEnterDestinationNode

When you call WalkToNode(NodeToWalkTo) it would search the road path pieces for the road that connects both of the nodes (current node, next node) and cache it.

The state machine would then walk from the current node to the path piece start. It would then walk the path, then when it gets to the destination node it would walk to centre of the node.

Another alternative is to adjust SLevelNode so that it carries the list of road pieces it needs.

struct SLevelNode
{
    CVector2D Position;
    CVector2D Size;
    CVector2D Origin;

    int ID;
    int Type;

    SLevelNode* pNeighbourNode[4];
    SPathPiece* pConnectingRoad[4];
};

For the finding of route between nodes you could use a recursive search for the destination node. i.e.

IsDestimationNodeInThisPath(Destination,Path)
{
    if(Path.ConnectedNode[0]==Destination)
    {
           return true;
    }
    else
    if(Path.ConnectedNode[1]==Destination)
    {
        return true;
    }

    if(!IsDestimationNodeInThisPath(Destination,Path.ConnectedNode[0])
    {
        if(!IsDestinationNodeInThisPth(Destination,Path.ConnectedNode[1])
        {
             return false;
        }
    }
}

The other thing you could do is adjust the above so it increases a reference count and return the length of path, the actual connecting nodes is then returned. That way you'd walk the quickest method rather than the first one found.

You'd also need the current node list so that if you visit the same node twice you bail out and return false because you are in a circular list.

This will go horribly wrong though if you increase the size of the map to much because it'll chew through stack.