Apply grids on a terrain

Newbie & Debugging Questions
#1

Hi, everyone.

I’m new to game programming, so I don’t have the experience to tackle this problem. I do have a hint of what might be the solution, but I don’t know if this is the optimal (or standard) way of solving the matter at hand.

Let me explain: In a TBS game, I will use A* for the pathfinding. Since my map is designed in 3D using Blender, how can I apply an invisible grid on it, to map its coordinates as “tiles”, in order to do the pathfinding? Must this be done in Blender, or in my 3D engine (JME)?

Also, how to map cost information to each “tile” in the terrain?

Or even, is the best approach to model only a “block” of the terrain, attaching cost information in a class representing this block, and render the entire map using a set of blocks?

Sorry for the questions if they’re noob, but I’ve searched in Google for insight and could not find something applying to my problem. :-[

Thanks in advance,

Son Of Cain

#2

… no one? :-\

#3

“Hey, i’m new to cars, i want to build a car! How should I connect the steer to the wheels? Should the doors open horizontally or vertically? Which engine do I need, I asked the local garage but they didn’t know…”

This is the style your questions have (IMO) and I wouldn’t have a clue how anybody could answer them, without asking you what you really mean.

You have to break down your problem in little pieces, and try to build every piece yourself first.

If you have any problem with actual code, feel free to post and you’ll get useful answers.

HTH :-\

#4

Hi,

Well, sorry then, I’ll try to be more specific.

My doubt does not rely on the engine I’m using, nor the format of my maps, or whatever; rather, All I hoped with the post was for someone to comment the standard solution used by games of the same sort, and then I would research it myself and try to tackle the problem while learning about it. That’s how I learn things, anyway.

I do know about A*, heuristics, and general pathfinding problems applied to it. I’m just asking if anyone has a tip on how to wire cost information on maps built on 3D tools like Blender. I don’t know if I should break my map into chunks and analyze the path from “chunk A” to “chunk B”, or if should do some sort of “scanning” on it prior to rendering in order to store cost information somewhere… all I want is a bit of advice from someone who has more experience than me.

And I’m not native of an english speaking country, so it is not so easy to express myself - I’m short where I should explain with more details, and I tend to overcomplicate what should be said simple and straightforward :-\

So I hope someone can give me tips on how one would wire A* cost information in scenarios for a TBS game.

Thanks in advance,
Son Of Cain

#5

Hi,
Even if your terrain model is imported from a File, you must have some kind
of ‘data model’ of it. This data model contains information like enemy spawn places,
treasure chest, etc.
About your project, is the terrain defined logically as 2D or 3D?? (Can two units be
on the same ‘tile’ but diferent heights?)
If 2D, I should make a editor tool with a top view of the terrain and a grid (the data
model) in wich you can set your values for the walk cost and other options.

 Hope this helps.
      Rafael .-
#6

Hi Rafael,

My maps are in 3D, and it is possible for an unit to be on the same tile on different heights ( say, a small cave, where an unit can be inside de entrance of the cave, and another one may be above it, or even a castle wall with a hole, which might picture the same case).

I understand the need of such a data model, so what’s the best approach to store information about terrain cost? Also, I need to control the map as a grid, because only one unit can stand one grid position at a time.

So, what should I store? A 3D matrix of “Vector3f” containing the position for each “block” of my terrain, with cost information and etc…?

Thanks for the help!

Son Of Cain

#7

The terrain is effectively a 2D plane with height information. If you slow (or stop) the character on steeper slopes, you should generate a cost that is the inverse of how fast the character can move. i.e. If your character can move 100 units per second, a flat area would have a cost of 0 while a sheer rock face would have a cost of 100.

Since you’re likely to have a coordinate system in place (it’s impossible not to), you can create “cells” by mapping the coordinate system to a small grid. e.g. If you have a 1000x1000 unit terrain and you want to use 10x10 unit cells (making the grid a 100x100 cell grid), you can always convert a character’s position with this code:


cellx = x/10;
celly = y/10;

The concept works the same in three dimensional space, except that there are dirrections above your head that are impossible to traverse. Normally, empty cells in the third dimension would be non-traversable. However, you may have to reevaluate the costs at runtime if you give certain characters the ability to fly.

In 3D space (say 1000x1000x1000 units with 10x10x10 unit cells which would make a volume of 100x100x100 cells) the computations to convert between coordinates and cells would be:


cellx = x/10;
celly = y/10;
cellz = z/10;
#8

** coding **

The flying character cost modifier can be attained by changing the heuristic used based on who is calling the algorithm, right? I store each heuristic as a class, and I apply a different heuristic in the calculation based on the “problem” I’m facing. Or is there a better way to handle this?

Thanks for the replies, guys! I appreciate your help!

Son Of Cain

#9

[quote=“Son_Of_Cain1,post:8,topic:26197”]
Or to put it in simpler terms, you have a different cost tables for different capabilities. :slight_smile:

#10

Hi!
For what TBS stands for? The following might not be quite suitable, but i use it for (mostly) open terrain FPS bots.

My concept, although prety much home-made and result of lots of experimentation is as follows: divide the terrain into areas. Areas can be collected by tracking player movement, and combining into larger areas.
Each area has some attributes (air, water, foliage, urban, inside building, VIP objective), position, size, and can contain child areas. Each area collects (learns?) statistics happening during actual gameplay, thus modifies the resulting cost. Areas are connected to other areas, representing passable terrain. The connections themselves collect statistics. Each AI has its own weights. The resulting cost of traversing from one area to the other is the sum of statistics each multiplied with a corresponding weight. A genetic algorithm could be applied to AI weights, thus making the AI more fit for the actual played map, but i’m not there yet.

Just realized that TBS stands for Turn Based Strategy, LOL. Forget this, this is for something on the other end of the games spectrum. LOL. And sorry, english isnt my native language either.

#11

I suppose TBS is Turn Based Strategy, but I used some time to figure it out too.

#12

What you are reaching for is a “walkmesh.”

There have been quite a few of articles on them recently in varying depth because NWN used one.

Keep in mind that a wealk mesh only works for 2.5D games, which is to say games where the player/monster objects feet are glued to the ground.

Id suggest googling “walkmesh”. You might also try flipping the indexes of books on RPG programmign in your local bookstore.

FInally, we just put back wlakmesh support in JNWN. At this point Im workign on an internally forked version but the last one I put abck to the external version I believe loads the walkmeshes and uses them for blocking tests.

#13

The search for “walk mesh” was a good shot, thanks Jeff.

I’ll stick to jbanes suggestion as of now, it seems to work nice for my requirements (at least I didn’t run into any problems, as of now =).

Thanks guys,

Son Of Cain

PS: BTW, TBS stands for “Turn Based Strategy”. Games like old Tactics Ogre and Final Fantasy Tactics are good examples, as well as most board games like chess. It is the counterpart of RTS (Real Time Strategy) games, where players take action concurrently. Obviously, in TBS, each player has a turn to act, either in sucession or randomly.