T2D Tutorial Creating a Path Point System

#1 OH!!! OH OH OH!!! OH !!! OH!H!!!!!!!!

This is WONDERFUL. My game pretty much depends on this. Thank you!

#2 Thanks King Tut, now all my units walk like an Egyptian:)

#3 Glad this helps lol... you all will need to show me some pics ;)

this isn't pathfinding but a system pathfinding will need to use, hopefully I can work on some sort of pathfinding solution and tutorial soon.

#4 Btw I actually do have a little 3d rendered sprite of a sphere to work as a better looking dot, though I didn't want people to have to download anything to work on the tutorial so I just used the stock tileMapImageMap lol...

#5 Hmm why did I bother doing that A* resource again? Apparently it ewas invisble and no one cares and just wants to replace it :p

#6 @John: I appreciate your AStar efforts too... I just admittedly haven't got to the point where I need AStar yet. Who says you can't use AStar and path points? I was actually planning on doing something like this:)

#7 Actually you normally would use them together. I Was more commenting on:

Quote:, hopefully I can work on some sort of pathfinding solution and tutorial soon.

#8 Your A* was good! Though truthfully not all games require A* and a lot of games require a highly modified A* :) For the RPG me and my team are working on we probaby won't use A*, though maybe some A* techniques combined with some custom setup

#9 Btw I was meaning pathfinding solution (for my team's game)... I often develop things for that then take a couple/few hours and make a tutorial to share my progress

#10

Quote:
Who says you can't use AStar and path points?

using John's AStar to place path points would be fairly efficient

#11 Lol I might as well share some of my design considerations (though I am not working on pathfinding yet, thats another reason for the comment, I still have it on a high level design down the road a bit)

This is the way I'm thinking it... I will probably create a custom pathFindingNode object... and a PathFinder object... the PathFinder will use pickLine (filtered by group and layer masks that are easily defined) to find paths around the entire levels... the pathFindingNode's will then be placed within LoS of eachother to effectively navigate the entire level (if you've used Unreal Ed then it will basically place all those nifty little apple things automagically, with specified groups to dodge around)

ok... this is just pathFindingNode plotting and finding techniques... still need to develop this lol... might extend C++ code to handle this for speed and efficiency, not sure though... I might do this before the game starts and save it with the level, or even before the game is released at all and save it to the level...

the object that follows these pathFindingNodes then will constantly check to ensure nothing is in the way, if it is it will either respond accurately or dodge it (different algorithms will be developed, some more advanced versions of my object avoidance code released in an earlier demo)...

ok I plan to have two types of pathfinding algorthims

1. AI units... I definately don't want a robust A* algorithm for each little baddie, unless I were to limit how many of them on screen, which I don't... Also this style of game won't require highly strategic movements...

These units will have simple checks, simple calculations to hop a ride on the shortest path...

1. Player unit... This will be more accurate and realistic, since the player will be seeing this constantly... though A* still probably won't be needed since the player will act as the strategic movement decided, but more accurate and constant checks will be required as well as other techniques to make the movement seem "smooth" vs "chompy" like other games


this is just some initial design concepts :) Figured I'd share it since we're on the topic

#12 Matt, nice tutorial. :)

With regards to RTSs and pathfinding, there are lots of ways to handle, as you're no doubt well aware.

Probably the most common trick for allowing pathing with lots of units is to force units that are close to each other and going to the same destination to follow a single path. This way, the path is only calculated once and lots of units can use it. You see this used in games like WarCraft 3. You can then have units then either move in a single-file line (as WC3 does for the most part) along the path, assuring that everyone stays on the path (so long as units don't get distracted by enemies, or what have you). Or, you can have them move in groups, using obstacle avoidance techniques on individual units and having units that get stuck or fall off the path meet up with their cohorts again by spawning individual, short path searches to figure how to get back to their crew.

Another common trick is to chunk pathing up into pieces. So, rather than doing an all-nodes search every time a path is asked for, sometimes the pathing grid is broken up into levels. The highest-level grid might be used for a quick check to determine what general direction a group of units should head in. From there, shorter path searches all called to get to an optimal destination in a chosen sub-region. This technique can lead to non-optimal paths for long-haul movements, but it's a nice optimization when long paths are requested.

Another important and common trick in RTS pathfinding is to not re-search known paths. In RTSs, players have the tendency to click-click-click their commands over and over when their in the heat of battle. If you take input and map it directly to commands, this repeated offering of commands means that your units will be continuously requesting the same path over and over. For many RTSs, depending on player habits, checking incoming commands against existing commands and culling incoming commands that are just repeats of current or recently issued commands can be a nice optimization. As an added benefit, this can save you from having to transmit repeated commands over a network a bunch of times in multiplayer games too.

Anyway, this doesn't have a lot to do with your tutorial in particular, but since you're working on this stuff for a game and you started sharing some of your pathfinding system design thoughts above, I thought I'd just chime in with these 3 common techniques real quick, in case you hadn't heard them before. :)

#13 Thx for the info Josh! Any input is always welcome...

The game I'll be designing this for will be a Diablo Style RPG... so won't really need RTS level of strategic moving... more along the lines, when the player is visible then it finds a path to them and attacks...

Great suggestions, in fact along the lines I'm thinking...

what I was describing before would be something done before even the level was loaded, so predefined paths would be already in place so the AI units wont have to do any major calculations... like what you are talking about with the single path, think I'm going to go with something along those lines, I'm not too worried if the AI units look like they're following a path because of the genre (more action based than strategy)...

Hopefully this will prevent me from having to add pathfinding nodes throughout all of the levels (like in Unreal Tournament =x)

so I will us the pathFinder object to already place the pathFindingNodes before the level even starts... (that is if I can get that to work right)... dynamically generated paths around a level basically


I definately like the chunked method... In fact I plan to do something along those lines, not sure exactly how I will specify it yet... maybe all pathNodes within a distance, or even group them upon placement by the pathFinder... but I plan to have a couple levels of them (like you explained better than I could lol- its similar to a bounding box /hit box idea for 3D collision... you check each major area then check the sub area so you don't have to check every area).

your last suggestion is my least thought out one... basic error checking (double checks etc) I do naturally (now at least)... though didn't think of the multiplayer aspects and keeping packets down, that I will definately have to optimize some

again thx for the comments... I still have to think/plan/ and develop a lot of this out so any input is great

#14 John: It would be cool if someone like you would show us how to convert Matt's tutorials using subclassing. Matt's stuff is awesome and everything I've learned so far about TScript has come from his generous work (thanks King Tut!), but i'm dying to know how to subclass.

For example, in my "test" game, I created a function called, ShowRank. Before Matt's "MoveTo" tutorial, it was a standalone function that was getting messed up and confused because too many objects were calling it at the same time:

function ShowRank(%Guy)
{
    if (!IsObject(%guy.rankSign)) {
       %Rank =new fxStaticSprite2D(){scenegraph =t2dSceneGraph;};
       %Rank.setImageMap(GetRankImage(%Guy.Rank));
       %Rank.setSize(%Guy.getSize()/2);
       %Rank.Mount( %Guy, "0 -.8", 0, false );

       %Guy.RankSign=%Rank;
       %rank.guy=%Guy;
    }
}

By extending the sceneobject class, it fixed all of my goofy, mysterous errors and eliminated a lot of schedule calls for clean-up:

function fxSceneObject2D::ShowRank(%this)
{
    if (!IsObject(%this.rankSign)) 
    {
        %Rank =new fxStaticSprite2D(){scenegraph =t2dSceneGraph;};
        %Rank.setImageMap(GetRankImage(%this.Rank) );
        %Rank.setSize(%this.getSize()/2);
        %Rank.Mount( %this, "0 -.8", 0, false );
    
        %this.RankSign=%Rank;
        %rank.guy=%this;
    }
}

Although that works, my %guy is the only object that needs a "ShowRank" method, so the obvious approach is to create a FighterObject subclass of fxSceneObject2D and put all of the specific methods / callbacks in there (there's many more than just ShowRank). That FighterObject should inherit everything from fxSceneObject2D. And If I want to create a subclass of FighterObject, I should be able to.

The other day I saw this topic:
Minimum linear velocity misbehavior? and behold I had found the Holy Grail! But it raises many questions. Do I need to modify / recompile the engine to get subclassing to work? What does each line do and do I need to follow this example like a template for it to work for my own custom class?

#15 You would either need to implement Bryan Edds OO in T2D resource or create a subclass of fxSceneObject2D in the C++ source code :)

(in fact I've been working on a tutorial for the later)

#16 heres the link for Object-Oriented Programming in T2D 1.0.0

#17 Thanks Matt, I check out that link.

I'm curious how Tim Doty did it, because that looks like TScript. I get the error "Link" command not found.

I was hoping 1.0.2 now allowed for OOP, but I guess not.

#18 Hes using the OOP in T2D resource ( that I linked above ) :)

I've been debating whether I should implement that or not... in the end for my team's final game I think I'll extend all the objects needed in the source code for efficiency, so I dont think I will... though wouldn't be hard later to do so since you can run those functions of fxSceneObject2D, just subdivide those functions out later if needed :)

EDIT: I suggest reading through all the comments before implementing it though, just so you know of any issues it has/may have

#19 Looks like a real pain. Why can't someone upload a compiled T2D.exe that has this already added?

#20 If you already have a compiler set up it shouldn't be hard to implement it :)

though I don't see why someone wouldn't be able to do that for you