• Register

Development Pillars:

  • View: 2D top-down with hidden line-of-sight (think Ulima IV: Quest of the Avatar)
  • Maps: Classic Dungeons & Dragons style tiles (Hexagonal for Wilderness, Square Grid for Dungeons)
  • Art: Old-School 80s/90s with simple pallets and 2-3 frame sprite animation supported with 2D black & white line art. Built for 2k resolution.
  • Platforms: Initially built to run on PC and cheap consoles (think FireTV) with later support for the others. So that means simple controls (D-pad) and a UI that supports it.
  • 3 Meter Gaming: This is an experience you should be able to enjoy from your couch on a large TV (as well as sitting in front of your PC). This drives toward a variety of design and art decisions that must be made.

Needed (for contract, commission, or partnerships):

avatar03Pixel Artist(s): We're looking for a pixel artist(s) to help build our world and define the style.

Narrative Writers: While we will eventually need writers for in-game quests, we are currently in need of short stories (approx 5-15 paragraphs) to help build out our in-game literary collection.

profile man022D (Pen/Ink) Portraits: We are in need of black & white portraits to be displayed in character conversation/dialogue boxes. Something similar to the kind of portrait you see to the right.

2D (Pen/Ink) Book Art: We also need artwork for in-game literature. Here is an article that describes the art we're looking for: Indiedb.com

Game Music Composer: We need a selection of game music to accompany the various gameplay states. For a description of our game music needs, see this post: Indiedb.com


  • View media
  • View media
  • View media
  • View media
  • View media
  • View media
Post article RSS Articles

Finding the path

News

Pathfinding in Classic CRPGs

(TLDR? There is a video at the bottom of this post.)

Classic CRPG pathfinding left a lot to be desired. And while we want to recreate the feel of those old CRPGs, nobody wants overly-dumb baddies. So, it was past time to finally upgrade the NPC pathfinding AI. (Before this, the system had the baddies move toward the player.) You know, something like this:

if (player.x < monster.x) monster.x--;

So, this project finally gave me a good reason to implement A* pathfinding.

NavMesh?

In most Unity projects, I'd simply recommend using the NavMesh system. It is a ridiculously powerful tool that has come in handy for me during a variety of past projects including everything from mobile arcade games to business apps in VR. But it seemed like overkill for a tile-based CRPG. If you want to know more about Unity's NavMesh, this guy's tutorial is a great intro.

navmesh


The A * Algorithm

So.. if I wasn't going to use Unity's NavMesh, everybody knows that the famous A* algorithm (pronounced "A STAR") is the best place to start for path-finding, but I had never actually implemented it from scratch. A quick Google search landed me on this guy's C# implementation. He references this other guy. A quick scan of those two and a read of the Wikipedia article to refresh myself on how it is supposed to work, I started coding and had the basic algorithm working in half an hour. It really is that straight forward. I can't believe it took me this long to give it a try.

pathfinding on a square grid


Of course there is a lot of nuance that goes into all of this after the basic implementation. For example:

  • Are all baddies really that smart (for suspension of disbelief or gameplay reasons)?
  • What are the limits of how long a path can be for performance reasons?
  • How often are paths recalculated (again, for performance)?
  • How do you account for dynamic objects?
  • Are the various terrain costs appropriately balanced?

But the big question before I started was the question of how well the A* algorithm would lend itself to the hex-grid. And as I should have expected, the answer is "beautifully... it handles hex-grids beautifully".

Basically, the algorithm tracks two lists, the "open list" and the "closed list". (The open list is just a list of all the cells we have noted that we want to do some calculations on and the closed list is all the cells we have already done some calculations on.)

Then we loop through the cells in the open list. And .... the first step in that loop is to add the current cell's neighbors into to the open list. In a square-grid you have four neighbors. In a hex-grid you have six. (See below)

four neighborsdirections


So for a hex-grid, we only have to place two more entries into the open list than we would if it was a square grid!

There is one small catch... What are the actual coordinates of those neighbors in the Unity Tilemap implementation?

Well, it depends on what row you are in.

  • If the y-value of the cell is even, then the NE and SE cells have the same x-value.
  • If the y-value of the cell is odd, then the NW and SW cells have the same x-value.

Lets see some code!

So my code for adding neighbors basically looks like this:

    static List<Vector3Int> AddNeighbors(bool p_isHex, Vector3Int p_pos)
    {
        if (!p_isHex)
        {
            Vector3Int[] allNeighbors =
            {
                new Vector3Int(p_pos.x + 1, p_pos.y, 0),
                new Vector3Int(p_pos.x - 1, p_pos.y, 0),
                new Vector3Int(p_pos.x , p_pos.y + 1, 0),
                new Vector3Int(p_pos.x , p_pos.y - 1, 0)
            };
            return new List<Vector3Int>(allNeighbors);
        }
        else
        {
            if (p_pos.y % 2 == 0)
            {
                //if y is even, we need to add the ne (x-1)(y+1)
                //if y is even, we need to add the se (x-1)(y-1)
                Vector3Int[] evenHexNeighbors =
                {
                new Vector3Int(p_pos.x + 1, p_pos.y, 0),
                new Vector3Int(p_pos.x - 1, p_pos.y, 0), 
                new Vector3Int(p_pos.x , p_pos.y + 1, 0),
                new Vector3Int(p_pos.x , p_pos.y - 1, 0), 
                new Vector3Int(p_pos.x - 1, p_pos.y + 1, 0),
                new Vector3Int(p_pos.x - 1, p_pos.y - 1, 0) 
                };

                return new List<Vector3Int>(evenHexNeighbors);
            }
            else
            {
                //if y is odd, we need to add the nw (x+1)(y+1)
                //if y is odd, we need to add the sw (x+1)(y-1)
                Vector3Int[] oddHexNeighbors =
                {
                    new Vector3Int(p_pos.x + 1, p_pos.y, 0), 
                    new Vector3Int(p_pos.x - 1, p_pos.y, 0), 
                    new Vector3Int(p_pos.x , p_pos.y + 1, 0), 
                    new Vector3Int(p_pos.x , p_pos.y - 1, 0), 
                    new Vector3Int(p_pos.x + 1, p_pos.y + 1, 0), 
                    new Vector3Int(p_pos.x + 1, p_pos.y - 1, 0) 
                };

                return new List<Vector3Int>(oddHexNeighbors);
            }
        }
    }

See it in Action

Okay, now add some debug lines to draw and things start to look great!

pathfinding on a hex grid


(Note that the Debug.DrawLine wasn't working for me, so I started with this DebugLine and modified it for my purposes.) You can find my updated DebugLine code at the bottom of this post.

Putting it all together in motion is where it starts to get fun. Here is a short video that makes it hard to believe it really was that easy!


Until next time, happy coding!

-John

Gameplay Video and Music Discussion

Gameplay Video and Music Discussion

News

Today is a quick update with the announcement of our uploaded gameplay video as well as an opportunity to discuss goals with our music tracks.

Building a Conversation System for CRPGs

Building a Conversation System for CRPGs

News

Simulating a conversation is one of the most challenging things for any CRPG! Lets talk a look at where traditional approaches may have gone wrong.

In Memory of Eric Bealer

In Memory of Eric Bealer

News

The brilliance of classic RPGs (Computer or Tabletop) is the artwork that inspires the imagination.

First Post

First Post

News

Using a hexagonal-grid for wilderness maps in combination with a square-grid for dungeon maps creates a great effect, but comes at a surprising cost on...

Add file RSS Files
DebugLine

DebugLine

Source Code

This is an update to DebugLine. It is adapted for my needs and maybe it's useful for you too. =

Comments
Famiklor
Famiklor

When will this game be released?

Reply Good karma Bad karma+1 vote
Post a comment
Sign in or join with:

Only registered members can share their thoughts. So come on! Join the community today (totally free - or sign in with your social account on the right) and join in the conversation.

Follow Report Profile
Icon
The Euphoria Project
Platforms
Windows, Mac
Creator
alaskajohn
Engine
Unity
Contact
Send Message
Release date
Game watch
Follow
Share
Style
Genre
Role Playing
Theme
Fantasy
Players
Single Player
Project
Indie
Embed Buttons
Link to The Euphoria Project by selecting a button and using the embed code provided more...
The Euphoria Project
Statistics
Last Update
Watchers
3 members
Files
1
Articles
5
You may also like
Legrand Legacy
Legrand Legacy Role Playing
Towards The Pantheon
Towards The Pantheon Role Playing
Vizaris
Vizaris Role Playing
Skullstone
Skullstone Role Playing
ARK: Survival Evolved
ARK: Survival Evolved Role Playing
Beastmancer
Beastmancer Role Playing