Okay, here's the scoop folks. I still have work to go before the 0.1.9 release, but I wanted to fill you in.
For the last week or so, I've been pounding my head on the keyboard trying to develop a working movement path algorithm. Everything works until I try to take mountains into effect. Some units cannot go through mountains, which affects their movement paths. However, the current engine does not take this into consideration
I have tried to find some way to find a work around. Right now, I have something that does the trick about 50% of the time.
I think I have figured out a solution. The design of the map is kinda like a W (see this):
☐■☐☐☐■☐
☐■☐■☐■☐
☐■☐■☐■☐
☐☐☐■☐☐☐
So, what I'm going to do is have four relay points.
For those of you who are curious what exactly I'm doing, you should first be familiar with the "A* Search Algorithm." Wikipedia has an article, but I found this one to be a little more relevant (and helpful).
Essentially, with my modified form, my game finds the "Delta X and Delta Y" (or together, the f value) for each point in a certain radius of the unit's start point. For each grid movement up-down or left-right takes one point. Thus, anything with an f-value from zero to the unit's max speed becomes a movable square.
I really have tried to make an algorithm that can steer around obstacles such as mountains, but alas, I have not been successful. So, the f-value for a grid is unaffected by mountains.
However, in my current workaround, the game detects where the unit is, and based on whether the unit is east or west of the mountains, adds to the f-value of squares to the left or the right of the mountains. This works fairly well, but it's not perfect.
I've been testing with the Cav Scout unit. This unit has a speed of 6. Most other units do not cause the problems that the Cav Scouts do when it comes to movement. However, if the Cav Scouts work, the other units will fall in line.
So, to compensate for the mountains, I will have four relay points. After I calculate the f-value and assign it to a relay point, the game will then use that point and calculate a new movement path. However, the radius will be f-value subtracted from the unit speed.
So, this will be what I do tomorrow (or, in a few hours rather). I will also add a couple last-minute convenience features, then the porting begins, which should take no time, now that I got Windows and Linux set up.
But, come hell or high water, whether this thing works or not, you will have some sort of demo tomorrow. I can't wait around on this forever!!
>=D
Subscribe to:
Post Comments (Atom)
About the pathing, if you are to mimic the original Advance Wars pathing, the anti-air in your screenshot would have no way of getting to the westernmost road/town, since the mountains are in its direct path, and it doesn't have enough speed to go around them.
ReplyDeleteAs such, you could assign each square a "dead" or "alive" value. If an obstacle(considered dead) is *between* the unit and other squares(with no other living squares adjacent) then said squares are also dead. As such they wouldn't even display on the movement grid. See http://img75.imageshack.us/img75/3001/warmachine.jpg
And from there on it's all downhill, you could apply your algorithm.
Thanks for the advice, Larry.
ReplyDeleteI actually have tried doing that. However, when the units enter than middle land, all hell breaks loose with the algorithm.
*groan* As i was saying before the power went out:
ReplyDeleteIf midfield path drawing/chosing was an issue, how did you implement it? Way I'd do it(and I think it might/should work fine) is select the crossable area in increments of 1 speed and you could only add a square to the crossable area if it's already adjent to a valid one.
See: http://img176.imageshack.us/img176/8613/warmachine2.jpg
That is... if all else fails, of course! :)
That's essentially what I've got now. I had to do some tinkering, but now the path movement should be pretty solid.
ReplyDeleteAwwesomesauce! :)
ReplyDelete