@bitassassin Interesting. Let me think about it. There are… tradeoffs. =)
1 Like
count me in my friend… 
1 Like
@Ponder Is it possible to implement a simple “Stop and rethink” hook at each native path-re-eval? We could handle all of the “Am I surrounded by sword swinging narwhals?” bits so long as we could essentially intercept and freeze pathfinding periodically, after which, if there is no change, we would just recall the pathing to the original coordinates.
I’m using my brain under the assumption that you have pathing check periodically to make sure the route is still available, i.e. the drawbridge hasn’t been raised, I haven’t soaked the countryside in lava/explosive pink goo, etc. and halt/update pathing if suddenly a meteor hits and there is a gaping chasm in your way. In that light I would believe (though C/C++ are not my strong suits) that implementing a flag for Lua checks there and if the flag is set, checking for the “Stop and rethink” hook wouldn’t be too bad.
The flag would be off by default (a config option maybe?) making it afaik a negligible performance hit to normal (non-modded) users:
1. 'Go from A -> B my little hearthenite!'
2. Flag check; Return 0; Rethink Flag is not on. Path directly as normal.
3. Get to B like a pro.
and for modded users:
1. 'Go from A -> B my little hearthenite!'
2. Flag check; return 1; Activate Lua Hook.
3. Check hook; No dice.
4. Path to finish. Commute.
and for modded users with AI hooks:
1. 'Go from A -> B my little hearthenite!'
2. Flag check; return 1; Activate Lua Hook.
3. Check hook; Present; ignore.
4. Path 0/10 to 1/10. Commute.
5. Check hook; Present; drop out to Lua AI
6. AI verifies that we aren't about to be murdered, let's Fred the other hearthenite know via the messaging system that we're going to get some grub.
7. AI Repaths to original dest.
8. Flag Check; return 1; act...
And so forth.
Now it isn’t to say that we couldn’t subdivide pathing on our own by hijacking the original pathing instruction, subdividing it and pathing to short intervals of the larger path while re-evaluating our environment along the way. So while some sort of integration into the actual native system would be super awesome-biscuits, so long as we are able to intercept, parse and subjugate user input to our will, we’ll be able to work around a black-box pathing algorithm.
ALSO THANKS FOR THE REPLY AND STUFF I ALMOST CHOKED ON MY LUNCH.
1 Like
Isn’t the alg they’re using A*? I’m sure I saw/heard that somewhere, if it is though all we need is some way of getting at the heuristic and we’d be able to control it fairly well. I’ll also support the idea of a community developed roguelike, and remember that you can cover js/html/css at some point as that will be needed for any modding that targets ui so a challenge related to that could work at some point.
I love the “AI Smackdown”-idea and hope that we will have some options to influence the AI of our fellows.
Not fully getting how the event-model works, but I was thinking it will support what you are describing @Xavion and @bitassassin. So instead of breaking down the path into smaller chunks and checking against a given condition, I thought the event-system will drop an event to the NPC and alert them if something is happening.
Assuming the settler walks from A to B and a meteor hits the path, the meteor will send an event to the NPC and he will process it. Processing might result into altering the path, or whatever reaction we might pre-define via Lua.
I think I might’ve been remembering names wrong but basically there is 2 parts of A* that would matter. The formula for calculating how much a given point in the grid costs to move through (e.g. mountains cost two and grassland costs 1), and the formula for distance to the finish (common ones involve going along the grid lines or going in a straight diagonal line). The second one doesn’t matter that much as it’s sole purpose nearly is to make it run faster, it can also be used to function as an accuracy(shortest path)/execution time modifier.
I’ve played around with A* before enough that I get how it works and stuff but I haven’t played around with in a non-grid based environment like stonehearth is so I’m not sure how they deal with that as it requires a network of points to move along. But what we’d do is modify terrain cost, so like if there was a battle we could tell warriors to try and avoid predicted paths of projectiles, or if there is some dangerous traps/locations we could say all civilians avoid this place X much and have X decrease to 0 over Y distance. Really though while writing this I’m having some trouble thinking of much uses to directly interfering with the pathfinding, mine are something that would likely be ridiculously advanced levels of AI and could be the start of really stupid stuff powerful stuff like shields with angles of incidence and deflection powers on one hand, and on the other something that should pretty much already be in the game what with how logical it is.
From what I can see most of the AI manipulation should deal with the adding of actions and the calibration of priorities, things like multi tasking and whether they go to the left or the right of the other person seem like overcomplex micro.
I love the idea of an AI smackdown - but isn’t there a problem here?
All players load the same mod. How do you have villagers controlled by different mods?
well, you can load several mods, that have varying behaviors that affect only specific types of units… so, you could have carpenters acting differently than blacksmiths… and even then, differences among the races or factions…
Just have an on/off toggle inside the game for the AI mods if you have to, or make a single competition mod and where you choose the ai you want from a list. There is plenty of ways to do it.
Preface: @SteveAdamo, please delete the above post so that this is not a double.
Alrighty, so, while I am still working on challenges. I have to gain a basic knowledge of TE-4 before I can issue challenges with it, and I am not a teacher or professional programmer by trade, so challenge Ideas via PM are welcome.
(I’m looking to you for help in this regard @Moghedrin, @Xavion, as both of you very likely have oodles more experience than I. Consider me more of a code maintaining QA Specialist and hobbyist programmer than anything else. To be as frank as possible, I modify pre-existing code extremely well and can wrap my head around most languages in about five minutes, but am poor in organizing and forming new code. This makes me a natural at modding, but not really at coding in general. [/humblebundle])
In light of the fact that challenges are taking a little bit longer (read: a lot longer) than anticipated, I will be using the next 20 minutes or so to address every single question and reply so far since my last activity. If you’re online, I’ll be continuing to answer any questions until 4:00pm PDT within 5-10min of their posting, similar to an AMA on Reddit.
So here are all of the answers going back:
With any luck, yes. But they have stated that the pathing system will be black-box native code and not moddable. To implement the pathing system in Lua would slow things down immensely, as per Team Rad in an earlier post/video/something. This Post:
Was addressing a possible solution to that, by creating event hooks for pathing accessible from the messaging system, that would essentially allow us to send a ‘break’ command to pathing if things go awry.
As to the second half of that post: www.w3schools.com, 'nuf said. That’s where I learned.
@voxel_pirate OH HAI AND WELCOME! Your thread makes me squee with mirth. Or some similar positive statement about your contributions.
In regards to the event model, that’s what I was concerned about. If pathing is black-box, we have no confirmation that such an ‘event receiver’ or hook as I called it in my post, would actually exist, causing pathing to always continue until the actual path fails (it reaches the chasm and can’t progress). That’s sort of (I was SO freaking tired when I wrote both of those) what I was trying to make sure Ponder implemented, though I couldn’t even wrap my own head completely around how it would function, what I was essentially asking for was a way to interrupt pathing based on environmental variables. Woot!
@Xavion in a non-grid game it can work slightly differently in some cases, but meh. Generally in this style of a game your movespeed modifiers are going to be your biggest detrimentals, otherwise the terrain is generally impassable. What we’re looking for are methods of allowing the units to perform their own micro. In pathing long distances there is a whole lot that can go wrong, and enemies can show up, archers can ambush you and traps can be detected and so forth. The hearthenites need some valid way of reassessing their situation mid-jog, and that is all I am addressing. If my hearthenite has a field of vision or there is any sort of fog-of-war, this will be essential, as one could walk around a corner and run into six goblins being all gobliny and stuff and without the ability to reassess, he would just keep on trucking. Or he could be pathing down a narrow hallway and suddenly he starts taking indiana damage from arrow turrets in the walls. Without the ability to reassess he would never turn around, and would just eat all of that damage. No bueno.
@Ramcat As @Xavion states AI Smackdown itself will be a mod (hopefully no dropdowns necessary). I’m going to be creating a small, simple API for the whole thing as well that will assign a small key to each mod to communicate with its hearthenites. No data would be allowed to be recognized by foreign hearthenites. Consider my mod a lower-level api to yours, preventing a sort of ‘tech war’ of trying to tell their hearthenites what to do. xD Remember that I still have to figure out a way to load two worlds in one first. That’ll be the biggest challenge, so I have to try not to get ahead of myself.
Alrighty, So that covers all replies before now! I’ll be here for the next hour to answer any other questions as well.
2 Likes
Be creative! Depending on how much you want to them to interact it could be anything from vm’s playing a mp game to segmenting a world into chunks and making them ignore each other, shouldn’t be too hard hopefully.
I kind of assumed that would have to be in it for basically the reasons you said, the main thing I can see getting at the pathfinding being really useful is large scale warfare and things like ambushes where going through one path or too close to an area can actually screw you up massively and where we could improve on the strategy that’s pre implemented using pathfinding.
I’ll try and think up some ideas for challenges and they’ll likely just be kinda basic things but for starters something project euler could work with a challenge of the day from it. As for experience I’m just a hobbyist that likes programming, I’ll tackle pretty much any task and because of it I can program. I’ve tried everything from writing scripting languages to n-dimensional mp computer games but really I just try whatever catches my attention and to learn new stuff.
i’ve removed the post, but just so you know, @Geoffers747 and i have a sort of “soft rule” in place, that grants the thread creator some slack within their own threads… 
and now, i will try and digest your massive wall of text… 
Somehow the “AI Smackdown” did not want to let me rest… an interesting topic once you have started to dig into further details. In my quest to understand more about AI, I have wrote a small script in Lua. It reads a playing field (6 x 6 squares) and determines where the actual position is, where the target is and where an obstacle is placed. After that, it assesses if the target is in the line of sight of the position.
It is a very basic script so far and has some shortcomings. Let me share the code (and I hope this is not considered as hijacking of this thread 
). Unfortunately discourse is not perfect for displaying code including comments (at least the way I write them). So I have uploaded the code to my webspace, including comments.
function DETERMINE_COORDINATES()
for i=1,6 do
for j=1,6 do
if playground_matrix[i][j] == 1 then
position_x = i
position_y = j
elseif playground_matrix[i][j] == 2 then
target_x = i
target_y = j
elseif playground_matrix[i][j] == 3 then
obstacle_x = i
obstacle_y = j
end
end
end
end
function LOS_ONE()
los_x = position_x
los_y = position_y
end_condition = 0
while end_condition == 0 do
if los_x == target_x then
if los_y > target_y then
los_y = los_y - 1
elseif los_y < target_y then
los_y = los_y + 1
end
elseif los_y == target_y then
if los_x > target_x then
los_x = los_x - 1
elseif los_x < target_x then
los_x = los_x + 1
end
elseif los_x > target_x and los_y > target_y then
los_x = los_x - 1
los_y = los_y - 1
elseif los_x < target_x and los_y < target_y then
los_x = los_x + 1
los_y = los_y + 1
elseif los_x > target_x and los_y < target_y then
los_x = los_x - 1
los_y = los_y + 1
elseif los_x < target_x and los_y > target_y then
los_x = los_x + 1
los_y = los_y - 1
end
if los_x == obstacle_x and los_y == obstacle_y then
los_result = 0
end_condition = 1
elseif los_x == target_x and los_y == target_y then
los_result = 1
end_condition = 1
end
end
return los_result
end
playground_matrix={}
for i=1,6 do
playground_matrix[i]={}
for j=1,6 do
playground_matrix[i][j]=0
end
end
playground_matrix[2][2]=1
playground_matrix[6][5]=2
playground_matrix[4][4]=3
position_x = 4
position_y = 4
target_x = 4
target_y = 4
obstacle_x = 4
obstacle_y = 4
los_result = 2
DETERMINE_COORDINATES()
print(position_x .. " " .. position_y)
print(target_x .. " " .. target_y)
print(obstacle_x .. " " .. obstacle_y)
LOS_ONE()
if los_result == 1 then
print("Target can be seen.")
elseif los_result == 0 then
print("Target is hidden.")
else
print("Something weird has happened.")
end
Back to the mentioned shortcomings…
- Very basic logic to determine the LOS.
- Only one obstacle can be placed at the moment.
- No check if positions make sense (e.g. target is not placed outside the playing field or not on the same field as the obstacle).
- … and for sure many, many others.
I do have some ideas to overcome one or the other point…
- Second and / or third LOS-logic could be included. Final result (if target can be seen) would depend on the fact that e.g. all are true.
- Existing logic could be adjusted to extend the radius which is assessed by the LOS-logic at the moment.
- Obstacles could be saved in an extra array to allow assessment against more than one obstacle.
I would love to hear if you “visitors of the bitcave” have any suggestions or comments…
2 Likes
hmmm… there is one big problem in this implementation, the path that LOS_ONE() chacks is incorrect.
for example, if the fild is set like this (yellow = position, gray = obstacle and red = target):
this script will move up twice, both in x and y, and then it will move twice to the right just on the x, causing a path that looks like this:
as you can see, the obstacle isn’t counts as “blocking the way”, but if you think about it it should! (imagine yourself standing in the yellow block, trying to look at the target), the correct path should look close to something like this:
as you can see its represents more correctly a straight line, and in this way the obstacle counts as “blocking the way”.
one way that i know of to achieve good representation of a straight line in a case like this is to use the Bresenham’s line algorithm.
if you are rally intrested in AI for games i would recommend a book called “AI for Game Developers” by David M. Bourg and Glenn Seeman (this is how i know this stuff), its a really good book, but I wouldn’t buy it just to mod stonehearth.
2 Likes
@jonyon54 Exactly. That is what I mean with “very basic logic”. At the moment the script is not assessing all situations right. In some (as in your example) the LOS is not blocked by obstacles. In some examples it is even the other way around and the LOS is blocked although the target should be visible. My idea to overcome this is to add other functions like “LOS_TWO()” and “LOS_THREE()” implementing different ways to check for the LOS and to add up all results. Just did not do it yet (as it was quite late yesterday).
I was not searching yet for hints on how to implement something similar, that kills all the creativity I think … but now that I have a basic setup implemented, I will take a look into your links. Thanks for that!
NB: I wrote most of this several hours ago and just didn’t hit post so it may seem to ignore the two most recent posts in part.
Analysis! Alrighty here we go, in any old order here are things to look into for improving it.
- Break statements, they can get rid of the end_condition stuff.
- Store the obstacles as a list of coordinates to allow for multiple
- You don’t actually have a 6x6 limit, your alg would work for any size if you put in other numbers.
- You can strip the giant if block to two statements to move it towards the target each time. Make them like so: los_x = los_x + (target_x-los_x)/abs(target_x-los_x)
And now for an improved los alg. First the one you have has two major issues, it’s slow having to loop through every intermediate square and it doesn’t work as shown in this rather bad image your code checks the brown path where it should be checking something similar to the red path.
Now for code to check the red path. What you need to do here is actually just run a rect line collision test and a rect rect collision test. First off for the rect rect test you just check whether the obstacle is within the rect by the target and position to see whether it’s possible to collide at all. Psuedocode follows
if obs_x >= min(pos_x, tar_x) and
obs_x <= max(pos_x, tar_x) and
obs_y >= min(pos_y, tar_y) and
obs_y <= max(pos_y, tar_y) then
test succeded
end
The line square collision is slightly more complex but still fairly simple. Treating the center of each square as the grid points it would go as follows.
gradient = (pos_y-tar_y)/(pos_x-tar_x)
if (obs_x - pos_x + 0.5*sign(gradient)) * gradient <=
(obs_y - pos_y - 0.5) and
(obs_x - pos_x - 0.5*sign(gradient)) * gradient >=
(obs_y - pos_y + 0.5) then
test suceeded
end
They rely on the fact that all obstacle are 1x1 squares but could be easily modified for rects of other sizes, other shapes would require more substantial changes however. It’s all a matter of how you do and what suits the scenario, checking every square is better when the path is shorter than the amount of obstacles and my example is better in the opposite.
2 Likes
i understand, just like you i usually like to think of solutions by myself, but its takes a lot of time to come up with efficient solutions this way, so usually, for the basic stuff, i use google and than code around it. this method is very basic in computer graphics so i thought its worth to mention it.
1 Like
… all i wanted to do is practicing some Lua coding and now I am ending up in a crash course in mathematics . Thanks for your both hints and comments.
Alrighty, First replies (If you would like to know why I’ve been scarce, skip to the bottom. But don’t do that!)
@voxel_pirate Your original post in no way hijacks! It’s the point of this thread! 
I’m still trying to digest all of your code, but so far it looks great. I’m excited to have the thread starting to grow organically, as that’s the way it should be. Everyone, ( @jonyon54 Welcome! @Xavion I swear to pickled olives you’re just smarter than I am. xD ) thanks for giving voxel your insight, as I am very good at encouragement, but mildly unable to actually debug or scrutinize code right now.
@Xavion Your analysis post is fantastic!
If I can figure out how to link these three posts in the main thread later, I’m totally doing it.
As to why I’ve been a little bit truant lately:
I’m currently in the process of winding down my employment with the company I’m with so I can move back to Portland. So I’ve been taking a ton of overtime to document the procedures and best practices I’ve formulated in the six months I’ve been with this company. It’s loads of work, but it’s helping me get down there with a tid-bit of a nest egg. I’ll be actually moving Mid-August, but until then my time for the thread is slim. Hell my time for gaming, life and sleep is slim right now. xD
I’d like to state for the record that all Mods @SteveAdamo @Geoffers747 (I believe you’re both mods, right? :wink2: ) are given permission to update links and such if I miss em or they find stuff. I wish there was a way I could temporarily turn over the reigns to a willing volunteer, (as after I post this I have about fifteen minutes of free time before going to take a four hour powernap and then going back to work), but I don’t think collaborative editing or thread-level moderation is a discourse feature.
So all in all, I’d like to apologize to everyone for not being independently wealthy… yet.
I’ll post when I can! See you all soon!
1 Like
as it sould be 
[quote=“bitassassin, post:62, topic:1622”]
@jonyon54 Welcome!
[/quote]
thanks